Dynamic programming solves problems by breaking them into
overlapping subproblems and caching results. The simplest
DP pattern is linear: dp[i] depends on a fixed number
of previous values.
Use when: the problem has optimal substructure (the answer builds on answers to smaller instances) and overlapping subproblems.
Climbing stairs: how many distinct ways can you climb to step n if you can take 1 or 2 steps at a time? This is the Fibonacci recurrence: dp[i] = dp[i-1] + dp[i-2].
We only need the last two values, so no array needed. This is the space optimization from O(n) to O(1).
House robber: maximize the amount you can rob from a row of houses where you can’t rob two adjacent houses. At each house, choose: rob it (skip previous) or skip it. dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Coin change: find the fewest coins to make a target amount. This extends the pattern to “min over choices”: dp[amount] = min(dp[amount - coin] + 1) for each coin.
Trace: climbStairs(5)
prev=1, curr=2 i=3: prev=2, curr=3 i=4: prev=3, curr=5 i=5: prev=5, curr=8 Answer: 8 ways
func climbStairs(n int) int {
if n <= 2 {
return n
}
prev, curr := 1, 2
for i := 3; i <= n; i++ {
prev, curr = curr, prev+curr
}
return curr
}
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
prev, curr := nums[0], max(nums[0], nums[1])
for i := 2; i < len(nums); i++ {
prev, curr = curr, max(curr, prev+nums[i])
}
return curr
}
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := range dp {
dp[i] = amount + 1
}
dp[0] = 0
for a := 1; a <= amount; a++ {
for _, coin := range coins {
if coin <= a && dp[a-coin]+1 < dp[a] {
dp[a] = dp[a-coin] + 1
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
func main() {
fmt.Println("Stairs(5):", climbStairs(5))
fmt.Println("Rob [2,7,9,3,1]:", rob([]int{2, 7, 9, 3, 1}))
fmt.Println("Coins [1,5,10] for 11:", coinChange([]int{1, 5, 10}, 11))
fmt.Println("Coins [2] for 3:", coinChange([]int{2}, 3))
}