动态规划-62.不同路径-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 15:58:15

810

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

一、题目解析

机器人只能向下或向左，要从Start位置到Finish位置。

二、算法原理

1.状态表示

我们要求到Finish位置一共有多少种方法，记Finish为[i,j]，此时dp[i,j]表示：到[i,j]位置时，一共有多少种方法，满足我们的需求。

2.状态转移方程

根据最近一步划分问题

3.初始化

开辟二维数组时，需要开辟(m+1)*(n+1)大小的空间，dp[0][0~n]和dp[0~m][0]用于初始化，其余dp[1][1]~dp[m][n]用于记录到达该位置的总方法数。

4.填表顺序

每行从左往右填写，每一列从上往下填写

5.返回值

由于Finish位置是[i][j]，所以结果返回dp[m][n]

可以先根据上面原理去尝试编写代码，链接：62. 不同路径 - 力扣（LeetCode）

三、代码示例

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        dp[0][1] = 1;
        for(int i = 0;i<=m;i++) dp[i][0] = 0;
        for(int j = 2;j<=n;j++) dp[0][j] = 0;
        for(int i = 1;i<=m;i++)
        {
            for(int j =1;j<=n;j++)
            {
                dp[i][j] = dp[i][j-1]+dp[i-1][j];
            }
        }

        return dp[m][n];
    }
};