dp[i][j]表示前i行、j列的路径数,状态公式如下:
- 如果
i >= 2 && j >= 2
,那么dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[1][k] = 1
dp[k][1] = 1
解释如下:
- 当列数和行数大于2的时候,当前节点的路径数为
左侧节点路径数
+右侧节点路径数
- 当列数或行数为1时,当前节点的路径数恒为1
代码如下:
// // Created by jt on 2020/8/30. // #include <vector> using namespace std; class Solution { public: /** * * @param m int整型 * @param n int整型 * @return int整型 */ int uniquePaths(int m, int n) { // write code here if (m < 1 || n < 1) return 0; if (m == n && m == 1) return 1; vector<vector<int> > dp(m+1, vector<int>(n+1, 0)); for(int i = 1; i <= m; ++i) dp[i][1] = 1; for(int i = 1; i <= n; ++i) dp[1][i] = 1; for (int i = 2; i <= m; ++i) { for (int j = 2; j <= n; ++j) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m][n]; } };