Dynamic Programming: From Fundamentals to Advanced Concepts

Core Concepts
Why Use Dynamic Programming
Common DP Patterns
Advanced DP Problems
Tips for Solving DP Problems
Space Optimization

Core Concepts

Dynamic programming (DP) is a problem-solving method that breaks down complex problems into simpler subproblems. It's based on two key principles:

Optimal Substructure: The optimal solution to a problem can be built from optimal solutions of its subproblems.
Overlapping Subproblems: The same subproblems are encountered multiple times when solving the larger problem.

Why Use Dynamic Programming

Consider calculating the nth Fibonacci number recursively:

1def fib(n):
2    if n <= 1:
3        return n
4    return fib(n-1) + fib(n-2)
5

This has a time complexity of O(2^n). With DP, we can reduce it to O(n):

1def fib_dp(n):
2    dp = [0] * (n + 1)
3    dp[1] = 1
4    
5    for i in range(2, n + 1):
6        dp[i] = dp[i-1] + dp[i-2]
7    return dp[n]
8

Common DP Patterns

Linear DP The simplest form where we build solutions in a linear fashion. Let's look at the classic "Climbing Stairs" problem:

1def climb_stairs(n):
2    if n <= 2:
3        return n
4    
5    dp = [0] * (n + 1)
6    dp[1] = 1  # One way to climb 1 stair
7    dp[2] = 2  # Two ways to climb 2 stairs
8    
9    for i in range(3, n + 1):
10        dp[i] = dp[i-1] + dp[i-2]
11    
12    return dp[n]
13

Two-Dimensional DP Used when the problem has two changing parameters. Consider the "Longest Common Subsequence" problem:

1def longest_common_subsequence(text1, text2):
2    m, n = len(text1), len(text2)
3    dp = [[0] * (n + 1) for _ in range(m + 1)]
4    
5    for i in range(1, m + 1):
6        for j in range(1, n + 1):
7            if text1[i-1] == text2[j-1]:
8                dp[i][j] = dp[i-1][j-1] + 1
9            else:
10                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
11    
12    return dp[m][n]
13

State Transition with Multiple Choices The "House Robber" problem demonstrates this pattern:

1def rob(nums):
2    if not nums:
3        return 0
4    if len(nums) <= 2:
5        return max(nums)
6    
7    dp = [0] * len(nums)
8    dp[0] = nums[0]
9    dp[1] = max(nums[0], nums[1])
10    
11    for i in range(2, len(nums)):
12        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
13    
14    return dp[-1]
15

Advanced DP Problems

String-Related DP Palindromic substrings is a classic hard problem:

1def count_palindromic_substrings(s):
2    n = len(s)
3    dp = [[False] * n for _ in range(n)]
4    count = 0
5    
6    # All single characters are palindromes
7    for i in range(n):
8        dp[i][i] = True
9        count += 1
10    
11    # Check for palindromes of length 2 and more
12    for length in range(2, n + 1):
13        for start in range(n - length + 1):
14            end = start + length - 1
15            
16            if length == 2:
17                dp[start][end] = (s[start] == s[end])
18            else:
19                dp[start][end] = (s[start] == s[end] and dp[start+1][end-1])
20            
21            if dp[start][end]:
22                count += 1
23    
24    return count
25

Optimization Problems The "Edit Distance" problem shows how DP can be used for optimization:

1def min_distance(word1, word2):
2    m, n = len(word1), len(word2)
3    dp = [[0] * (n + 1) for _ in range(m + 1)]
4    
5    # Initialize first row and column
6    for i in range(m + 1):
7        dp[i][0] = i
8    for j in range(n + 1):
9        dp[0][j] = j
10    
11    # Fill dp table
12    for i in range(1, m + 1):
13        for j in range(1, n + 1):
14            if word1[i-1] == word2[j-1]:
15                dp[i][j] = dp[i-1][j-1]
16            else:
17                dp[i][j] = min(
18                    dp[i-1][j] + 1,    # deletion
19                    dp[i][j-1] + 1,    # insertion
20                    dp[i-1][j-1] + 1   # replacement
21                )
22    
23    return dp[m][n]
24

State Compression DP For problems with large state spaces, we can use bit manipulation to compress states. Here's an example with the "Traveling Salesman Problem":

1def traveling_salesman(distances):
2    n = len(distances)
3    all_visited = (1 << n) - 1
4    
5    dp = {}
6    
7    def solve(mask, pos):
8        if mask == all_visited:
9            return distances[pos][0]
10        
11        state = (mask, pos)
12        if state in dp:
13            return dp[state]
14        
15        ans = float('inf')
16        for city in range(n):
17            if mask & (1 << city) == 0:  # if city is not visited
18                new_ans = distances[pos][city] + solve(mask | (1 << city), city)
19                ans = min(ans, new_ans)
20        
21        dp[state] = ans
22        return ans
23    
24    return solve(1, 0)  # Start from city 0
25

Tips for Solving DP Problems

Identify the Subproblem Structure

Break down the problem into smaller, similar subproblems Determine how solutions to subproblems combine

Define State Variables Clearly

Choose appropriate variables to represent each state Ensure states capture all necessary information

Write the Recurrence Relation

Express the solution to the current state in terms of previous states Consider all possible transitions

Determine Base Cases

Identify the simplest scenarios Ensure they're handled correctly

Implementation Choice

Decide between bottom-up (tabulation) and top-down (memoization) Consider space and time trade-offs

Space Optimization

Many DP solutions can be optimized for space. For example, Fibonacci can use constant space:

1def fib_optimized(n):
2    if n <= 1:
3        return n
4    
5    prev2, prev1 = 0, 1
6    for _ in range(2, n + 1):
7        current = prev1 + prev2
8        prev2 = prev1
9        prev1 = current
10    
11    return prev1
12

This guide covers the essential concepts and techniques in dynamic programming. Practice is key to mastering these concepts. Start with simpler problems and gradually work your way up to more complex ones, always focusing on understanding the patterns and problem-breaking techniques.

Back