Grokking Dynamic Programming (Part 2)

Hey everybody! I'm Mike Roks, and this is the second part on solving Dynamic Programming problems. In the first part, we mentioned the base principle of solving all DP problems: Finding a 'question' to 'ask' for input (X) - large X so that:

1. Answer is "Given" (obvious, known)
2. Or can be always calculated using answers for (x) - small x, where (x) is an input "smaller" (simpler, in the context of a given task, logically ordered before) than (X). We saw this method working with an example of Fibonacci numbers, and now, let's use it to solve a more complicated task.

Medium - Unique Paths ()

We have a robot, which starts at the top-left corner. They can move down & right. We need to calc all the unique ways for the robot to get to the right-bot corner.

Remember, we need to find such a 'question' so the answer is either obvious or can be formed from previous answers. We want to know the number of ways the robot can get into the FINISH cell. The robot can get to FINISH either from the cell one higher than it or one lefter.

1. So, to get to cell 20, the robot HAS to go either from cell 19 or through cell 13, And there is only one way to go from 19 to 20 (make a step right), and only one way to get from cell 13 to the cell 20 (make a step down). So all the possible paths to cell 20 == (all the possible paths to cell 13) + (all the possible paths to cell 19).

2. We can get to cell 19 from cells 18 & 12 in the exact same manner.

3. To cell 13 - from 12 & 6 (you can already see 12 being used several times, so it's a good idea to cache it)

4. To cell 6 we can only get from cell 5, so the total amount of ways to cell 6 is the same amount as to cell 5 (as there is only one way to get from 5 to 6 - just go righter from 5).

   
   

And so on until we consider cell 1 & cell 7. We can get there only from the cell 0.

The robot starts at cell 0. How many ways are there to get from cell 0 to cell 0? This is a ridiculous question, so we just need to figure out the number which would make sense. If we say, "there are 0 ways to get to cell 0", so by our calculation, the number to get to cell 1 would be 0, to cell 7 == also 0, to cell 8 == (0+0), so also 0, and all the cells would have "0 ways to get to them". Saying there is > 1 way is unreasonable, as cell 0 is the initial cell, and we are given no information that there were prior branches in paths to get to it. Saying there is exactly one way to get to cell 0 would mean there is one way to cell 1, 1 to cell 7, and two to cell 8, and it makes sense.

So our `base case` is - there is 1 way to get to cell 0, and we can get the number of paths to the current cell by looking up & left. If cell exists, we += its number of paths, else not.

We have all of the necessary parts to solve this problem.

The question is - "what is the number of ways to i, j (row, column)"?

The answer is:

if i == 0 and j == 0, then 1

else if i < 0 or j < 0, then also 0

else sum(by i-1, j; by i, j-1)

Let's code it out:

class Solution {
    int[][] g;
    public int uniquePaths(int m, int n) {
        g = new int[m][n];
        g[0][0] = 1;
        return paths(m-1, n-1);
    }


    //paths i, j
    //  if oob ret 0
    //  if in g > 0 -> ret g[i][j]
    //  else return paths i-1, j + paths j, i-1


    int paths(int i, int j) {
        //if oob, then 0
        if(i < 0 || j < 0) return 0;
        //if cached - from cache
        if(g[i][j] > 0) return g[i][j];
        //if not in cache - calc
        int res = paths(i-1, j) + paths(i, j-1);
        //record calced to cache
        g[i][j] = res;
       
        return res;
    }
}

We could enhance the Space Complexity of this solution, but it's not necessary for the purposes of this article - we managed to decompose a complex problem statement to a question by the generic pattern & solved it.

**That's it, folks, like, share, subscribe! :D