LeetCode 63. 不同路径 II

和62.不同路径 | 类似，多加一些限制条件即可。 

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] a=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(obstacleGrid[i][j]==1){
                    continue;
                }
                if(i==0&&j==0){
                    a[i][j]=1;
                }else if(i==0){
                    a[i][j]=a[i][j-1];
                }else if(j==0){
                    a[i][j]=a[i-1][j];
                }else {
                    a[i][j]=a[i-1][j]+a[i][j-1];
                }
            }
        }

        return a[m-1][n-1];
    }
}

 

 另外：

何时使用【回溯】，何时使用【动态规划】，用大白话说，就是：

1. 首先看取值范围，递归回溯一维数组，100就是深度的极限了（何况本题是100²）
2. 如果是求走迷宫的【路径】，必然是回溯；如果是走迷宫的【路径的条数】，必然是dp--------(这个竟然屡试不爽！！！！)