DynamicProgramming

This is a easy way to learn Dynamic Programming

DP is known as bottom-up and top-down.
Top-down is like a recursion, but with memoized, when using top-down, draw tree.
Bottom-up is like careful brute force, you need to track all the subquestions’ answer for further use.

This is a picture from MIT course that explain the fib questions use bottom-up, I actually like bottom-up way, because it is easy to understand, you need to draw a table to find the optimal solution, although you can use it for fib one.

Here are some dp classic questions.

1. *Find a Path***

​ Leetcode 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] nums =new int[m][n];
        for(int[] b: nums ){
            Arrays.fill(b, 1);
        }
        for(int i=1; i< m; i++){
            for(int j=1;j<n;j++){
                nums[i][j]=nums[i-1][j]+nums[i][j-1];
            }
        }
        return nums[m-1][n-1];
    }
}

63.*Unique Paths II***

robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row=obstacleGrid.length;
        int col=obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1){
            return 0;
        }
        obstacleGrid[0][0]=1;
        for(int i=1;i<row;i++){
            obstacleGrid[i][0]=(obstacleGrid[i][0]==0 && obstacleGrid[i-1][0]==1)? 1:0;
        }
        for(int j=1;j<col;j++){
            obstacleGrid[0][j]=(obstacleGrid[0][j]==0 && obstacleGrid[0][j-1]==1)? 1:0;
        }
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if(obstacleGrid[i][j]==0){
                    obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
                }
                else{
                    obstacleGrid[i][j]=0;
                }
            }
        }
        return obstacleGrid[row-1][col-1];
    }    
}