63.unique-paths.ii.md

63. Unique Paths II

Bottom-Up DP

Pay attention on the base case [0, 1, 0, 0, 0], if there is one obstacle in the first row or column, then the following item after that obstacle will be unreachable (path will be zero), so the dp will be [1, 0, 0, 0, 0].

fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
    val m = grid.size
    val n = grid[0].size
    if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return 0

    val dp = Array(m) { IntArray(n) }
    // Base cases:
    // For obstacleGrid = [0, 1, 0, 0], it initializes the dp to [1, 0, 0, 0] all the right and down side will be 0 if encounter one obstacle.
    var has0 = false
    for (c in 0 until n) {
        if (grid[0][c] == 1) has0 = true
        dp[0][c] = if (has0) 0 else 1
    }

    has0 = false
    for (r in 0 until m) {
        if (grid[r][0] == 1) has0 = true
        dp[r][0] = if (has0) 0 else 1
    }

    for (i in 1 until m) {
        for (j in 1 until n) {
            if (grid[i][j] == 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
    }
    return dp[m - 1][n - 1]
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Bottom-Up DP (Space Optimization)

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

               dp[i - 1][j]
                     |
                     v
dp[i][j - 1] ->  dp[i][j]

We can reduce the 2D array into 1D array (for dp[i - 1][j]) with left (for dp[i][j - 1]) value, we can just use dp[j] = d[j] + dp[j - 1].

dp[0, 1, ..., j - 1, j]
   |  |         |
   v  v         v
dp[0, 1, ..., j - 1  ?

When the time we calcluate dp[j], dp[j - 1] will be updated and it becomes left value, so we can get rid of left, just use dp[j - 1].

/**
 * Edge case:
 * 1
 * 0
 */

private fun bottomUpSpace(grid: Array<IntArray>): Int {
    val m = grid.size
    val n = grid[0].size
    // if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return 0 // Optional
    val dp = IntArray(n)
    // Used for base case
    var firstColHas0 = grid[0][0] == 1
    var firstRowHas0 = grid[0][0] == 1
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (i == 0 && j == 0) {
                dp[0] = if (grid[i][j] == 1) 0 else 1
            }
            else if (i == 0) {
                if (grid[i][j] == 1) firstRowHas0 = true
                dp[j] = if (firstRowHas0) 0 else 1
            } else if (j == 0) {
                if (grid[i][j] == 1) firstColHas0 = true
                dp[0] = if (firstColHas0) 0 else 1
            } else {
                dp[j] = if (grid[i][j] == 1) {
                    0
                } else {
                    dp[j] + dp[j - 1]
                }
            }
        }   
    }
    return dp[n - 1]
}

// Or equivalent
fun uniquePathsWithObstacles(grid: Array<IntArray>): Int {
    val m = grid.size
    val n = grid[0].size
    val dp = IntArray(n)
    dp[0] = if (grid[0][0] == 1) 0 else 1
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (grid[i][j] == 1) {
                dp[j] = 0
            } else if (j > 0) {
                dp[j] += dp[j - 1]
            }
            // dp[0] will be the same if not obstacle, otherwise 0.
        }
    }
    return dp[n - 1]
}

• Time Complexity: O(m * n)
• Space Complexity: O(n)

WA of Bottom-Up DP (Space Optimization)

下列做法在進入主循環之前就把整個第一欄 dp[0] 掃過一遍，導致後續每一列的 dp[0] 都不是該列的正確值。

我們初始化 dp 後，又起了另一個 has0 在主迴圈前就把第一欄從上到下掃完，最後 dp[0] 只剩下最後一列的值，當我們進入主迴圈的時候，dp[0] 永遠都是最後一列的值，這樣就錯了。

真正的做法是：當我們在主迴圈開始逐列 for (i in 1..m-1) 在更新時，在每一列的開始就更新該列的 dp[0]，這樣 dp[0] 就會是該列的正確值。dp[0] 應該跟著每一個 row 去更新，而不是一開始就先掃完第一欄更新完。

private fun bottomUpSpace(grid: Array<IntArray>): Int {
    val m = grid.size
    val n = grid[0].size
    // Initialize base case for the first row ->
    val dp = IntArray(n)
    var has0 = false
    for (j in 0 until n) {
        if (grid[0][j] == 1) has0 = true
        dp[j] = if (has0) 0 else 1
    }
    // WA: Iterate the first column to initialize dp[0]
    has0 = false
    for (i in 0 until m) {
        if (grid[i][0] == 1) has0 = true
        dp[0] = if (has0) 0 else 1
    }

    // Iterate the rest of the grid other than the first row and column
    for (i in 1 until m) {
        for (j in 1 until n) {
            dp[j] = ...
        }   
    }
    return dp[n - 1]
}