Medium Grid DP 2-D Dynamic Programming
In plain English: Count the number of ways to walk from the top-left to the bottom-right of a grid, only moving right or down.
dp[i][j] = number of ways to reach cell (i,j). Each cell can only come from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. Optimize to a single row since we only look at the previous row.
Prompt
A robot is in the top-left corner of an m x n grid. It can only move right or down. How many unique paths are there to the bottom-right corner?
Try to write it from scratch before scrolling down.
Solution
def unique_paths(m, n):
row = [1] * n # base: top row all 1s
for i in range(1, m):
for j in range(1, n):
row[j] += row[j-1] # above + left
return row[-1]
# Test: unique_paths(3, 7) == 28
# Test: unique_paths(3, 2) == 3