62/63-不同路径

LeetCode 62. Unique Paths

LeetCode-62

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Example 1:

Input: m = 3, n = 7
Output: 28

method: 动态规划

当前位置只能从左边或上边过来

注意初始化：第一行和第一列都是1

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 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 - 1][n - 1];
}

改进

因为只跟上一行有关，所以只需要两行就可以了

int uniquePaths(int m, int n) {
    vector<int> pre(n, 1), cur(n, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            cur[j] = cur[j - 1] + pre[j];
        }
        swap(cur, pre);
    }
    return pre[n - 1];
}

再改进

只需要一行就够了，在下一次i循环cur就变成pre了

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

---

LeetCode 63. Unique Paths II

LeetCode-63

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

method

初始化问题：对于第一行和第一列，如果出现障碍，就不能再继续赋值了，因为已经过不去了

int uniquePathsWithObstacles(vector<vector<int>>& map) {
    int m = map.size(), n = map[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    for (int i = 0; i < m && map[i][0] == 0; i++) {
        dp[i][0] = 1;   // 出现障碍就退出
    }
    for (int j = 0; j < n && map[0][j] == 0; j++) {
        dp[0][j] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (map[i][j]) continue;    // 障碍dp保持0
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}