不同路径 II - 力扣（LeetCode）

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        int dp[100][100]={0};
        for (int i = 0; i < m && obstacleGrid[i][0]==0; i++)
            dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j]==0; j++)
            dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j]) dp[i][j]=0;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

把int dp[100][100]={0};放到class外面之后结果就会不同

int dp[100][100]={0};
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        for (int i = 0; i < m && obstacleGrid[i][0]==0; i++)
            dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j]==0; j++)
            dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j]) dp[i][j]=0;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

这是为什么？现在还没找到答案。

还有我最初的想法

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int dp[101][101]={0};
        int m=obstacleGrid.size(),n=obstacleGrid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0) dp[i+1][j+1]=1;
                else dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j];
                if(obstacleGrid[i][j]) dp[i+1][j+1]=0;           
            }
        }
        return dp[m][n];
    }
};

双重循环中的语句顺序调换一下结果就会不同

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int dp[101][101]={0};
        int m=obstacleGrid.size(),n=obstacleGrid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0) dp[i+1][j+1]=1;
                if(obstacleGrid[i][j]) dp[i+1][j+1]=0;   
                else dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j];
            }
        }
        return dp[m][n];
    }
};

这又是为什么啊？