Posts

Classic Dynamic Programming XII

-
Image
This type of DP is the one that still doesn't come naturally to me (and yes, I took a look at the hints!). The combination of different XORs along the paths are indeed exponential, but the key is to see that the possible values of the cells are all < 1024. Every XOR then will land somewhere between 0-1023. With that information, we can DP it by using a matrix of DP[rows][cols][1024], and keep track of any path that lights up any of the bits between 0-1023. The cleanness of the code is striking, it is very "symmetrical" when it is set and done, however the mental model is still non-intuitive (IMO) since you're using the values of grid as indexes of the DP. Code is down below, cheers, ACC. Minimum XOR Path in a Grid - LeetCode You are given a 2D integer array  grid  of size  m * n . You start at the  top-left  cell  (0, 0)  and want to reach the  bottom-right  cell  (m - 1, n - 1) . At each step, you  may  move either  ri...
Post a Comment
Read more

This is a Graph Problem - Not a Tree Problem! Part IV

-
Image
I think this problem had everything: hashtables, hashsets, recursive DFS and non-recursive DFS and even applications of the dangerous .GetHashCode(), which I don't like but sometimes it is good enough when the constraints are limited, which is the case of this problem. But the problem isn't a tree problem - it is a graph one. Convert the tree to a graph (needed because you'll be navigating up and down the tree), and that's where I'm using .GetHashCode() to uniquely identify the nodes (worked), then for each node (non-recursive DFS) perform a search (recursive DFS) looking for the max path, traversing only in the case of unique numbers. Notice that you need to keep going even if you find a -ve node since there might be a larger unvisited number behind that node. Code is down below, cheers, ACC. Maximum Distinct Path Sum in a Binary Tree - LeetCode You are given the  root  of a  binary tree , where each node contains an integer value. A  valid path  in the tree is...
Post a Comment
Read more