不同路径

题目

具体思路

1. 当前的结果 来自从上方来的路径 + 从左侧来的路径
2. 初始化肯定是将 res[1][1] = 1 即在起点时只有一条路径；
3. 对于各条边的处理，我们将结果的下标与存储的下

具体实现

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] res = new int[m + 1][n + 1];
        res[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                res[i][j] = res[i - 1][j] + res[i][j - 1];
            }
        }
        return res[m][n];
    }
}

保存每一轮的结果

class Solution {
    public int uniquePaths(int m, int n) {
        int[] res = new int[n + 1];
        res[1] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                res[j] += res[j - 1];
            }
        }
        return res[n];
    }
}

// 1 1 1 1  1  1  1  1 1
// 1 2 3 4  5  6  7  8
// 1 3 6 10 15 21 28 36

压缩成二维数组， r e s [ j ] = r e s [ j ] + r e s [ j − 1 ] ，从左边来的结果与上一次的结果，但是不必每次都保存上一轮的结果。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

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