dp[i][j]表示前i行、j列的路径数,状态公式如下:

  1. 如果i >= 2 && j >= 2,那么dp[i][j] = dp[i-1][j] + dp[i][j-1]
  2. dp[1][k] = 1
  3. dp[k][1] = 1

解释如下:

  1. 当列数和行数大于2的时候,当前节点的路径数为左侧节点路径数+右侧节点路径数
  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];
    }
};