https://leetcode-cn.com/problems/unique-paths/

image.pngimage.png

思路一：排列组合

image.png

  1. var uniquePaths = function(m, n) {
  2.     let res = 1;
  3.   for(let i = 0; i < Math.min(m - 1, n - 1); i++) {
  4.       res *= m + n - 2 - i;
  5.     res /= i + 1;
  6.   }
  7.   return res;
  8. };

思路二：动态规划

机器人只能向右或者向下移动一步。

所以从左上到右下的走法 = 从右边开始走的路径总数 + 从下面开始走的路径总数

所以动态方程为：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

这样就可以通过递归解决了。

而第一行和第一列时的值为

  • dp[0][j] = 1
  • dp[i][0] = 1

这是因为一直向下或者一直向右的话，只有一种走法

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