DSA · Chapter 37 of 40
Dynamic Programming
Dynamic programming solves problems that have overlapping subproblems and optimal substructure by solving each subproblem once and reusing the result. Top-down DP adds memoisation to recursion; bottom-up DP fills a table iteratively.
The hard part is defining the state: what exactly does dp[i] mean? Once the state and transition are clear, the code is short.
Steps
1) Define the state. 2) Write the transition (recurrence). 3) Set the base cases. 4) Decide the iteration order. 5) Optionally reduce space.
Classic problems
Fibonacci, climbing stairs, house robber, coin change, longest common subsequence, 0/1 knapsack and edit distance.
Example 1 (python)
def climb(n):
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(climb(5))Output
8dp[i] = number of ways to reach step i.
Example 2 (python)
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for c in coins:
for a in range(c, amount + 1):
dp[a] = min(dp[a], dp[a - c] + 1)
return -1 if dp[amount] == float('inf') else dp[amount]
print(coin_change([1, 3, 4], 6))Output
2DP finds 3+3 where greedy would answer 3 coins.
Key points
- DP needs overlapping subproblems and optimal substructure.
- Memoisation is top-down; tabulation is bottom-up.
- Defining the state clearly is the main difficulty.
- Many 1D DP solutions can be reduced to O(1) space.
💡 Note: Say your state definition out loud in the interview — it is half the answer.