[[Dynamic Programming Primer]]

Problem

You are on an m x n grid. You start at the top-left corner (0, 0). Your goal is to reach the bottom-right corner (m-1, n-1). At any point, you can only move right or down. Find the total number of unique paths.

Brainstorming

Well 2D dp is back , and this time it is not as crazy as the previous 2 times. The idea here we are discussing is how many unique paths can we use to reach path from top left to bottom right. Given that we can only move right and down the problem can be thought of as:

Story of a single cell

at cell (i,j) how many ways can we reach this cell? since we can only move right and down it means we can only reach (i,j) from either the left or the top and thats the core definition of our problem

so the dp state is defined as Number of ways you can reach cell (i,j)

and the recurrence equation becomes

dp[i][j] = NUMBER OF WAYS YOU CAN REACH FROM LEFT + NUMBER OF WAYS YOU CAN reach from TOP

Now what about the base case to floor the calculations? lets look at the first row grid[0][j] there is only one way we can reach all the columns in the first row Let’s think about dp[0][2]. To get there, you must have come from dp[0][1]. There is no other path. You don’t add a “new” way; you simply carry over the number of ways from the previous cell. The number of paths is the number of paths to the cell on the left.

• `dp[0][1] = dp[0][0] = 1
• `dp[0][2] = dp[0][1] = 1
• dp[0][3] = dp[0][2] = 1

hence the recurrence rule becomes

Number of ways you can reach to the left of grid[0][j]

same is true for the first column grid[i][0] the only way we can reach all the rows in this is from the top so the recurrence equation becomes

Number of ways you can reach to the top of the grid[i][0]

but what about the first cell ? grid[0][0] how many ways can we reach this? well since we don’t have any cell before this or above this there are 0 ways to reach this cell

This is a very logical conclusion, but it leads to a problem. If dp[0][0] = 0, then:

- dp[0][1] (ways to reach the cell to the right) would be dp[0][0], which is 0.
- dp[1][0] (ways to reach the cell below) would be dp[0][0], which is 0.
- Then dp[1][1] would be dp[0][1] + dp[1][0] = 0 + 0 = 0.
- The entire grid would fill with zeros!

This is the same trap as in Climbing Stairs with dp[0]. We need an anchor. The question is “how many ways to get to the start?”. By definition, there is one way to be at the start: by starting there.
So, dp[0][0] = 1

Now lets try to write this algorithm

1. Initialise the dp grid as the same size as our matrix with 0 values
2. dp[0][0] =1 this is the floor for our calculations
3. then we will write a loop that will fill all the values in the first row of the with 1
4. we will do the same for the first column as well fill its value with 1
5. now we will traverse the grid from the top left all the way to the bottom right and use our recurrence equation dp[i][j] = dp[i-1][j]+ dp[i][j-1]
6. And the final answer lies in dp[m-1][n-1]

below is the python implementation

m = 5
n = 3

dp = [[0 for _ in range(n)] for _ in range(m)]

dp[0][0] = 1 # base case 1
 
# base case 2 the top row
for i in range(1,m):
	dp[i][0] = 1

# base case 3 the first column 
for j in range(1, n):
	dp[0][j] = 1


for i in range(1, m):
	for j in range(1, n):
		dp[i][j] = dp[i-1][j] + dp[i][j-1]
		
# final answer
print(dp[m-1][n-1])

cleaner version

m = 5
n = 3

# Create an m x n grid and initialize ALL cells to 1.
# This automatically handles all base cases for the first row and column.
dp = [[1 for _ in range(n)] for _ in range(m)]

# Now, the main loops can start from (1, 1) and just apply the recurrence.
for i in range(1, m):
    for j in range(1, n):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

# The final answer is in the same place.
print(dp[m-1][n-1])