DP on grids for counting paths, minimal costs, and shapes
dp[r][c] depends on neighbors (up/left/diag) under constraints, often with obstacles.
Use for path counting, minimal path sum, or maximal shape areas in grids.
Initialize first row/col and transition from neighbors (up/left/diag); apply row compression when only previous row is needed.
# Interval DP Template (Matrix Chain)
def matrix_chain(dims):
n=len(dims)-1
dp=[[0]*n for _ in range(n)]
for L in range(2, n+1):
for l in range(0, n-L+1):
r=l+L-1; dp[l][r]=10**18
for k in range(l, r):
dp[l][r]=min(dp[l][r], dp[l][k]+dp[k+1][r]+dims[l]*dims[k+1]*dims[r+1])
return dp[0][n-1]Count routes with allowed moves
def unique_paths(m, n):
dp=[[1]*n for _ in range(m)]
for i in range(1,m):
for j in range(1,n): dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[m-1][n-1]Accumulate minimal sum to cell
def min_path_sum(grid):
R,C=len(grid),len(grid[0]); dp=[[0]*C for _ in range(R)]
dp[0][0]=grid[0][0]
for i in range(1,R): dp[i][0]=dp[i-1][0]+grid[i][0]
for j in range(1,C): dp[0][j]=dp[0][j-1]+grid[0][j]
for i in range(1,R):
for j in range(1,C): dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1])
return dp[R-1][C-1]DP for squares/rectangles of ones
def maximal_square(matrix):
R,C=len(matrix),len(matrix[0]); dp=[[0]*C for _ in range(R)]; best=0
for i in range(R):
for j in range(C):
if matrix[i][j]=='1':
dp[i][j]=1 if i==0 or j==0 else 1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
best=max(best, dp[i][j])
return best*bestVisit each cell.
Row compression often possible.