Different paths ii[dynamic planning improvement for DFS]

Preface

Dynamic programming , Common space for time , Especially for DFS for , Reduce a lot of unnecessary double counting .

One 、 Different paths II

Two 、DP + In situ space utilization

package everyday.medium;

//  Different paths II
public class UniquePathsWithObstacles {
    
    /* target： Go from the upper left corner of the matrix to the lower right corner , Possible ways , You can't walk where there are obstacles .  The first idea is DFS+ Over obstacles , however DFS There are many repeated sub paths , So you can exchange space for time , With dynamic programming .  Each grid comes from the left or the top , So you can calculate how many ways to walk to the lower right corner step by step . //  notes ： Tips , In situ modification matrix , Use it , Reduce space complexity . */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
        //  because 1 Indicates an obstacle ,0 Indicates accessibility , So when modifying the matrix in place , Use a negative number to indicate the possible number of paths .
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        //  A special case , If both the starting point and the ending point are obstacles , You don't have to go .
        if (obstacleGrid[0][0] == 1 || 1 == obstacleGrid[m - 1][n - 1]) return 0;

        obstacleGrid[0][0] = -1;
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                //  If it's an obstacle , Then it is not necessary to calculate .
                if (obstacleGrid[i][j] == 1) continue;
                int up = i == 0 || obstacleGrid[i - 1][j] == 1 ? 0 : obstacleGrid[i - 1][j];
                int left = j == 0 || obstacleGrid[i][j - 1] == 1 ? 0 : obstacleGrid[i][j - 1];
                //  The current grid is the end point , The number of possible paths is   Coming from the left  +  On the right .
                // bug1: When i == j == 0 when , The initialization of the -1 Also covered , All for 0
                // obstacleGrid[i][j] = left + up;
                obstacleGrid[i][j] += left + up;
            }
        }
        //  Return to the bottom right corner , Number of possible paths .
        return -obstacleGrid[m - 1][n - 1];
    }
}

summary

1） Dynamic programming .

reference

[1] LeetCode Different paths II