时间轴

2026-03-21

init

题目：

P62 不同路径

https://leetcode.cn/problems/unique-paths/description/?envType=study-plan-v2&envId=top-100-liked

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
using std::vector;

class Solution {
    public:
        int uniquePaths(int m, int n)
        {
                int i, j;
                vector<vector<int> > dp(m, vector<int>(n, 0));
                // dp[i][j] 表示到(i,j)的不同路径总数
                for (i = 0; i < m; i++)
                        dp[i][0] = 1;

                for (j = 0; j < n; j++)
                        dp[0][j] = 1;

                for (i = 1; i < m; i++) {
                        for (j = 1; j < n; j++)
                                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }

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