62. 不同路径

题目链接

解题思路

• 方法一：暴力递归，process(i, j)，当前在[i, j]位置，到达右下角有多少种方法？

  • 如果i < m - 1，那么可以往下走，所以结果加process(i + 1, j)

  • 如果j < n - 1，那么可以往右走，所以结果加process(i, j + 1)

  • 因为只有两个可变参数，所以直接加缓存即可。

  • 代码

    class Solution {
    public:
        int process(const int m, const int n, int i, int j, vector<vector<int>> &dp) {
            if (i == m - 1 && j == n - 1) {    // 到达右下角了  答案+1
                return 1;
            }
            if (dp[i][j] != -1) {
                return dp[i][j];
            }
            int ans = 0;
            if (i < m - 1) {    // 没有到达最后一行 可以往下走
                ans += process(m, n, i + 1, j, dp);
            }
            if (j < n - 1) {    // 没有到达最后一列，可以往右走
                ans += process(m, n, i, j + 1, dp);
            }
            dp[i][j] = ans;
            return ans;
        }
        int uniquePaths(int m, int n) {
            vector<vector<int>> dp(m, vector<int>(n, -1));
            return process(m, n, 0, 0, dp);
        }
    };
    

• 方法二：其实就是一个数学题，从左上角，到右下角，一共有n + m - 2步，所以就是n + m - 2步中，拿出n - 1步往右走C(n - 1, n + m - 2)。

  • 代码

    class Solution {
    public:
    
        // 用longlong防止溢出
        long long process(int a, int n) {     // 计算C(a, n)
        if (a == 0) {
            return 1;
        } 
            long long ans = 1;
            for (int i = 1; i <= a; ++i) {
                ans = ans * (n - i + 1) / i;
            }
            return ans;
        }
    
        int uniquePaths(int m, int n) {
            if (m < n) {   // 谁小算谁
                return process(m - 1, n + m - 2);
            }
            return  process(n - 1, n + m - 2);
        }
    };