Dynamic programming (DP) is a powerful algorithmic technique used to solve optimization problems by breaking them down into smaller, overlapping subproblems. The key insight is that many complex problems can be solved efficiently by storing solutions to subproblems and reusing them.
The longest increasing subsequence problem exemplifies two crucial properties that make dynamic programming applicable:
Optimal Substructure: The optimal solution contains optimal solutions to subproblems. If we know the longest increasing subsequence ending at each position before index i, we can compute the longest increasing subsequence ending at position i by extending the best previous subsequence.
Overlapping Subproblems: When computing the LIS for different positions, we repeatedly need to know the LIS lengths for previous positions. Instead of recalculating these values, we store them in a DP table.
The general DP approach involves:
For sequence problems like LIS, a common pattern is to let dp[i] represent the optimal solution ending at position i. This allows us to build up solutions incrementally, considering how each new element can extend or improve previous solutions.
1def count_ways_to_climb_stairs(n):
2 """Count ways to climb n stairs, taking 1 or 2 steps at a time."""
3 if n <= 2:
4 return n
5
6 # dp[i] = number of ways to reach step i
7 dp = [0] * (n + 1)
8 dp[1] = 1 # One way to reach step 1
9 dp[2] = 2 # Two ways to reach step 2
10
11 for i in range(3, n + 1):
12 dp[i] = dp[i-1] + dp[i-2] # Recurrence relation
13
14 return dp[n]