62. different paths - Dynamic Planning

One 、 Title Description

A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）.

The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish” ）.

Ask how many different paths there are in total ？

Example 1：

 Input ：m = 3, n = 7
 Output ：28

Example 2：

 Input ：m = 3, n = 2
 Output ：3
 explain ：
 From the top left corner , All in all  3  Path to the bottom right .
1.  towards the right  ->  Down  ->  Down 
2.  Down  ->  Down  ->  towards the right 
3.  Down  ->  towards the right  ->  Down 

Example 3：

 Input ：m = 7, n = 3
 Output ：28

Example 4：

 Input ：m = 3, n = 3
 Output ：6

Two 、 Problem solving

Dynamic programming

How many paths in total ： dp[i][j] = dp[i-1][j] + dp[i][j-1];

Expand ： Shortest path ： dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+1;

class Solution {
    
    public int uniquePaths(int m, int n) {
    
        // Dynamic programming problem 
        int[][] dp = new int[m][n];
        // First fill in the first line 
        for(int i = 0;i<n;i++){
    
            dp[0][i] = 1;
        }
        // Fill in the first column 
        for(int i = 0;i<m;i++){
    
            dp[i][0] = 1;
        }
        // Walk the inner ring 
        for(int i = 1;i<m;i++){
    
            for(int j = 1;j<n;j++){
    
                // Shortest path 
                // dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+1;
                // How many paths in total 
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];

    }
}