Unique Paths (DP)
Question:
There is a robot on an m*n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2*10^9.
Solutions:
We know our base case is position 0,0. We can move either down or right. For recursion and using top-down approach, we’ll start from the target. and we’ll move towards our base case.
def unique_paths_helper(m: int, n: int) -> int:
if m == 0 and n == 0:
return 1
elif m < 0 or n < 0:
return 0
else:
down_m = unique_paths_helper(m, n-1)
right_m = unique_paths_helper(m-1, n)
return down_m + right_m
def unique_paths(m: int, n: int) -> int:
return unique_paths_helper(m-1, n-1)
print(unique_paths(3, 7)) # prints 28
print(unique_paths(3, 2)) # prints 3The recursion tree for 3,2 would look like this:
The runtime complexity for the algorithm is O(2^n) where n is the height of the tree.
The space complexity is also O(m*2^n) where m is the space of each recursive call and n is the height of the tree.
As we know there are repetitions of computation, see node 1,0, let’s use caching to prevent it. This technique is called memoization.
from typing import List
from collections import defaultdict
def unique_paths_helper(m: int, n: int, memo: List[int]) -> int:
if m == 0 and n == 0:
return 1
elif m < 0 or n < 0:
return 0
elif (m,n) in memo:
return memo[(m,n)]
else:
down_m = unique_paths_helper(m, n-1, memo)
right_m = unique_paths_helper(m-1, n, memo)
memo[(m,n)] = down_m + right_m
return memo[(m,n)]
def unique_paths(m: int, n: int) -> int:
memo = defaultdict(int)
return unique_paths_helper(m-1, n-1, memo)
print(unique_paths(3, 7)) # prints 28
print(unique_paths(3, 2)) # prints 3With memoization, we have saved repetitive computation. We also added extra O(m*n) space where m is the number of rows and n is the number of columns.
Runtime complexity is O(m*n) where m is the number of rows and n is the number of columns.
Space complexity is also O(m1*m*n) + O(m*n)where m1 is the space of each recursive call, m number of rows, and n number of columns.
Now let’s come to the Dynamic Programming (DP) part. For the DP, two things to remember is recognize the subproblem and use the subproblem’s solution to build the target’s solution; bottom-up approach!
For the subproblem we know that if there was only a row or only a column, there would be only one way. For other rows and columns, we use both right and down movement’s result to build the current position’s result.
def unique_paths(m: int, n: int) -> int:
dp = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
print(unique_paths(3,7)) # prints 28
print(unique_paths(3,2)) # prints 3The runtime complexity is O(m*n) where m is the number of rows and n is the number of columns.
The space complexity is O(m*n) as well where m is the number of rows and n is the number of columns.
Now let’s do part 2 of the question.
Question:
You are given an m*n integer array grid. There is a robot initially at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2*10^9 .
The implementation is similar to part 1 but this one has additional constrain to take into account.
Solutions:
Here’s the recursive solution:
from typing import List, Tuple, Dict
from collections import defaultdict
def unique_paths_helper(obstacle_grid: List[List[int]], m: int, n: int) -> int:
if m == 0 and n == 0:
return 1
elif m < 0 or n < 0:
return 0
else:
right_m = down_m = 0
if obstacle_grid[m][n] != 1 and m >= 1:
right_m = unique_paths_helper(obstacle_grid, m-1, n)
if obstacle_grid[m][n] != 1 and n >= 1:
down_m = unique_paths_helper(obstacle_grid, m, n-1)
return right_m + down_m
def unique_paths(obstacle_grid: List[List[int]]) -> int:
m = len(obstacle_grid)-1
n = len(obstacle_grid[0])-1
return unique_paths_helper(obstacle_grid, m, n)
obstacle_grid0 = [[0,0,0], [0,1,0], [0,0,0]]
print(unique_paths(obstacle_grid0)) # print 2
obstacle_grid1 = [[0,1], [0,0]]
print(unique_paths(obstacle_grid1)) # prints 1The recursive tree for obstacle_tree = [[0,0,0], [0,1,0], [0,0,0]] looks like this:
The runtime complexity is O(2^n) where is the height of the tree.
The space complexity is O(m*2^n) where m is the space required for each recursive call and n is the height of the tree.
To avoid repetitive computation, we’ll cache already computed position. Here is the memoized solution:
from typing import List, Tuple, Dict
from collections import defaultdict
def unique_paths_helper(obstacle_grid: List[List[int]], memo: Dict[Tuple[int, int], int], m: int, n: int):
if m == 0 and n == 0:
return 1
elif m < 0 or n < 0:
return 0
elif (m,n) in memo:
return memo[(m,n)]
else:
right_m = down_m = 0
if obstacle_grid[m][n] != 1 and m >= 1:
right_m = unique_paths_helper(obstacle_grid, memo, m-1, n)
if obstacle_grid[m][n] != 1 and n >= 1:
down_m = unique_paths_helper(obstacle_grid, memo, m, n-1)
memo[(m,n)] = right_m + down_m
return memo[(m,n)]
def unique_paths(obstacle_grid: List[List[int]]) -> int:
memo = defaultdict(int)
m = len(obstacle_grid)-1
n = len(obstacle_grid[0])-1
return unique_paths_helper(obstacle_grid, memo, m, n)
obstacle_grid0 = [[0,0,0], [0,1,0], [0,0,0]]
print(unique_paths(obstacle_grid0))
obstacle_grid1 = [[0,1], [0,0]]
print(unique_paths(obstacle_grid1))Runtime complexity: O(m*n) where m is the number of rows and n is the number of columns.
Space complexity: O(m1*m*n) + O(m*n)where m is the number of rows, n is the number of columns and m1 is the space taken for each recursive call.
Now let’s go do the Dynamic Programming (DP) implementation!
We know that if there’s only one row and there’s an obstruction we cannot reach the destination and vice-versa to only one column. Using this as our subproblem, we’ll build our target’s solution.
from typing import List
def unique_paths(obstacle_grid: List[List[int]]) -> int:
m = len(obstacle_grid)
n = len(obstacle_grid[0])
dp = [[0]*n for _ in range(m)]
# 0th column
for i in range(m):
if obstacle_grid[i][0] == 1:
break
else:
dp[i][0] = 1
# 0th row
for j in range(n):
if obstacle_grid[0][j] == 1:
break
else:
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] != 1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
obstacle_grid0 = [[0,0,0], [0,1,0], [0,0,0]]
print(unique_paths(obstacle_grid0))
obstacle_grid1 = [[0,1], [0,0]]
print(unique_paths(obstacle_grid1))Runtime complexity: O(m*n) where m is the number of rows and n is the number of columns.
Space complexity: O(m*n) where m is the number of rows and n is the number of columns.
That’s it for this post! Congratulations on reaching this far! 🎈 Hope DP is getting fun! 💪
See you next time. Until then, ✨.
Inspirations:
You can support me on Patreon!
