Force deduction 62 different paths (the number of all paths from the upper left to the lower right of the matrix) (dynamic planning)

        Today I come across a dynamic programming problem that I think is very valuable . From this question , I feel I have a deeper understanding of Dynamic Planning , You can see that it doesn't help you .

---

First look at the topic ：

A robot is in a m x n  The top left corner of the grid , The robot can only move down or right one step at a time . The robot tries to reach the lower right corner of the grid and asks how many different paths there are ？

Example

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

answer ： 

From the title , You can only move down or right at a time

From this we infer ===》  The number of paths to a grid , Determined by its left grid and upper grid  

From this we infer ===》 Here we can use the idea of dynamic programming to solve

From this dynamic equation ===》 dp[i][j] = dp[i-1][j] + dp[i][j-1]

---

thus , We have solved half the problem , Then we think about the first column and the first row , Because you can only move down or right at a time , therefore Each grid in the first row can only be moved to the right from the grid on its left , So the first line dp[0][j] All for 1, The first column of lattice is the same .

This concludes the analysis , List codes

    public int uniquePaths(int m, int n) {
        int[][] dp = new int [m][n];
        for(int i=0;i<n;i++){
            dp[0][i] = 1;
        }
        for(int i=0;i<m;i++){
            dp[i][0] = 1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

 

Okay , That's all for this article , Favorite students can like the collection , Have a problem , Can comment , Or leave a message , I will give you feedback at the first time , Thank you for watching. ！！

notes ： This article is for me to share my learning experience , There are mistakes or areas that need to be corrected , Please correct me. , I will accept with an open mind