力扣62 不同路径(从矩阵左上到右下的所有路径数量) (动态规划)

        今天遇到一道个人认为很有价值的动态规划问题。从这道题里，个人感觉对动态规划有了更深刻的了解，大家可以看看对自己又没有帮助。

---

先看题目：

一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角问总共有多少条不同的路径？

示例

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

解答： 

由题目得知，每一次只能向下或者向右移动

由此我们推知 ===》 到达一个格子的路径数量，由它左边格子和上边格子所决定 

由此我们推知 ===》 这里可以使用动态规划的思想来解决

由此动态方程 ===》 dp[i][j] = dp[i-1][j] + dp[i][j-1]

---

至此，我们已经解决一半的问题了，然后我们再思考第一列和第一行，由于每一次只能向下或者向右移动，所以第一行的每个格子都只能由它左边的格子向右移动而来， 所以第一行dp[0][j] 都应该为1，第一列格子同理。

至此分析结束，列出代码

    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];
    }

 

好了，这次的文章就到这里，喜欢的同学可以点赞收藏，遇到问题，可以评论，或者留言，我一定会第一时间给到回馈，感谢观看！！

注：本文为本人学习时心得分享，有讲错或者需要改正的地方，请指正，我会虚心接受