Dynamic Programming Review

## Introduction to Dynamic Programming - **Definition**: Dynamic programming is an algorithmic technique that solves complex problems by breaking them down into simpler subproblems and storing the results to avoid redundant calculations. - **Overlapping Subproblems**: The same smaller problems appear multiple times when solving the larger problem. Instead of recalculating these subproblems repeatedly, we store their solutions. - **Optimal Substructure**: The optimal solution to the problem contains optimal solutions to its subproblems. This means we can build up the best solution by combining the best solutions to smaller parts. ## Dynamic Programming Solutions - **Memoization (Top-Down Approach)**: Memoization stores the results of expensive function calls and returns the cached result when the same inputs occur again. ```py def climb_stairs_memo(n, memo={}): """Dynamic programming with memoization""" # Check if we've already calculated this value if n in memo: return memo[n] # Return cached result - O(1) lookup! # Base cases if n <= 2: return n # Calculate once and store in memo for future use memo[n] = climb_stairs_memo(n-1, memo) + climb_stairs_memo(n-2, memo) return memo[n] ``` - **Tabulation (Bottom-Up Approach)**: Tabulation builds the solution from the ground up, filling a table with solutions to subproblems. ```py def climb_stairs_tabulation(n): """Dynamic programming with tabulation""" if n <= 2: return n # Create array to store results for all steps from 0 to n dp = [0] * (n + 1) dp[1] = 1 # 1 way to reach step 1 dp[2] = 2 # 2 ways to reach step 2 # Build up the solution iteratively for i in range(3, n + 1): # Ways to reach step i = ways to reach (i-1) + ways to reach (i-2) dp[i] = dp[i-1] + dp[i-2] return dp[n] ``` ## Real-World Applications Using Dynamic Programming - **Route Optimization**: GPS systems use dynamic programming algorithms to find shortest paths between locations. - **Text Processing**: Spell checkers and autocomplete features often rely on dynamic programming to calculate edit distances between words. - **Financial Modeling**: Investment strategies and portfolio optimization frequently employ dynamic programming techniques. - **Resource Allocation**: The knapsack problem and its variants appear in scheduling, budgeting, and resource management. ## When to Use Dynamic Programming You should consider using dynamic programming in the following scenarios: - The problem can be broken down into overlapping subproblems. - The problem exhibits optimal substructure. - A naive recursive solution would involve repeated calculations. - You need to optimize for time complexity at the cost of space complexity.