Skip to main content

Classic DP Problems

Master these fundamental dynamic programming problems that form the foundation for more complex DP challenges.

Fibonacci & variations​

  • Basic Fibonacci: F(n) = F(n-1) + F(n-2) with base cases F(0)=0, F(1)=1
  • Climbing Stairs: Number of ways to reach top (same as Fibonacci)
  • House Robber: Maximum money without robbing adjacent houses
  • Min Cost Climbing: Minimum cost to reach top of stairs

Climbing stairs​

  • Problem: Count ways to reach nth step (1 or 2 steps at a time)
  • DP State: dp[i] = number of ways to reach step i
  • Recurrence: dp[i] = dp[i-1] + dp[i-2]
  • Base Cases: dp[0] = 1, dp[1] = 1

House robber​

  • Problem: Maximum money from non-adjacent houses
  • DP State: dp[i] = maximum money from first i houses
  • Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  • Base Cases: dp[0] = 0, dp[1] = nums[0]

Coin change​

  • Problem: Minimum coins needed to make target amount
  • DP State: dp[i] = minimum coins for amount i
  • Recurrence: dp[i] = min(dp[i-coin] + 1) for all coins
  • Base Case: dp[0] = 0

Longest common subsequence​

  • Problem: Length of longest common subsequence between two strings
  • DP State: dp[i][j] = LCS length for first i chars of string1 and first j chars of string2
  • Recurrence: dp[i][j] = dp[i-1][j-1] + 1 if chars match, else max(dp[i-1][j], dp[i][j-1])
  • Base Cases: dp[0][j] = 0, dp[i][0] = 0