LeetCode: Unique Path II

Question

• https://leetcode.com/problems/unique-paths-ii/
• Level: Medium
• Type: DP | DFS or BFS

Core Logic

Main

• In Unique Path I, we made a DPVector, meaning 'unique path to reach current index'
• Which is pretty much same logic, and same meaning[DPVector], but we have a constraints here though
  • If current index is BLOCKED, that means we cannot access to current index, so we set to dpVector[curIndex] to zero.
• Also, in Unique Path I, we assumed all paths are accessible, but there is a case that you cannot access. Like picture below.
  • 1 is blocked, and 0, 0 is start, and 3, 2 is the end.
    
• So we must not initiate all dpVector to 1 if (i == 0 || j == 0).
  • There is an exception, like above picture.
• But still, DP Equation would be dpVector[curindex] = dpVector[top] + dpVector[left] if there is no exception.

Number of Exceptions

• When starting point[0, 0] is blocked
  • Obviously, we cannot reach to destination, since even starting point is blocked.
• When Reach point is blocked
  • Also, trivial, we cannot reach, so return 0.
• When whole row or column is blocked.
  • Since we are NOT initiating our first row/columns all-ones[See pic above], so this will be handled through normal algorithm

Algorithm

• Create DP Vector
• Iterate through DP Vector[iteration index: i/j]
  • If both i/j are 0,
    • Set to dpVector[i][j] to 1 if i/j is NOT blocked
    • otherwise, return 0.
    • continue;
  • If i is zero
    • set dpVector[i][j] = dpVector[i][j-1]; // Append previous[left] one
    • If i/j is blocked, just set to zero.
  • If j is zero
    • Trivial, same as when i is zero, unless we are handling j instead.
  • Any other case
    • If i/j is not blocked, set dpVector[i][j] = dpVector[i-1][j]+dpVector[i][j-1]
• return last index of DPVector

Submission