【学会动态规划】不同路径（5）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】不同路径（5）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：62. 不同路径 - 力扣（Leetcode）

【学会动态规划】不同路径（5）,学会动态规划,动态规划,算法,c++

题目的要求也很容易理解，

机器人只能往右或者往下走，

求从起点走到终点有多少种情况。

2. 算法原理

1. 状态表示

那么 dp[ i ][ j ] 表示什么呢？

dp[ i ][ j ] 就表示走到 [ i，j ] 位置的时候，一共有多少种方式。

2. 状态转移方程

根据最近的一步划分问题，因为机器人只会往右和往下走，

那么dp[ i ][ j ] 就等于从上来的方法数 + 从左边来的方法数

所以 dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1 ]

3. 初始化

因为第一行和第一列没有上面和左边的数，

所以第一行和第一列的方法数都是1，所以我们直接初始化成1，

然后从dp[ 1 ][ 1 ]开始遍历。

4. 填表顺序

直接从左往右，从上往下即可。

5. 返回值

返回题目要求的终点位置即可：dp[ m - 1 ][ n - 1 ]。

3. 代码编写

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 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];
    }
};