34. 不同路径 II

题目

示例

解析

1. 令f[i][j]存储：从 (0, 0) 到 (i, j) 的路径个数
2. 而一步到 (i, j) 最多只有两个路径：从左面或者从上面
3. 那么，接下来判断，是否能从左面或者上面到 (i, j)，如果可以，那么 f(i, j) 加上左面或者上面的路径个数即可

代码

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    if(obstacleGrid[0][0])
        return 0;
    vector<vector<long long> > f(m, vector<long long>(n));
    f[0][0] = 1;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++) {
            // if(i || j) f[i][j] = 0; （可有，可无，因为 ：f默认都是0）
            if(!obstacleGrid[i][j]) {
                if(i) f[i][j] += f[i - 1][j];
                if(j) f[i][j] += f[i][j - 1];
            }
        }
    return f[m - 1][n - 1];
}

疑问

f为int型， 为什么会报错 ？？？

Line 27: Char 65: runtime error: signed integer overflow: 1053165744 + 1579748616 cannot be represented in type 'int' (solution.cpp)