[summery] [leetcode] Unique path2 | 机器人带障碍（简单例子demonstrate 2wayDP变1way）

Posted by: lexigrey on: November 2, 2013

• In: leetcode | summery
• Leave a Comment

• d[i][j]表示从(0, 0)到(i, j)有几种走法，因为只能从上面来或从左边来，所以每次计算只需要d[i – 1][j]和d[i, j – 1]，左上角的全都浪费了。
• f[i]表示从(0,0)到(当前row, j)有几种走法，上面来的就是自己，左边来的已经算好了，所以 f[j] = f[j] + f[j – 1];

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    // one way DP, f[i] means from (0, 0) to (currRow, i) has how many ways
    int f[] = new int[n];
    f[0] = obstacleGrid[0][0] > 0 ? 0 : 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) { //comes from above or left 
            if (obstacleGrid[i][j] > 0) {
                f[j] = 0;
            } else {
                if (j == 0) //first col only from above
                    f[j] = f[j];
                else 
                    f[j] = f[j] + f[j - 1];
            }
        }
    }
    return f[n - 1];
}

Tags: 1WayDP, 2WayDP