Definition: A design technique that combines brute-force correctness and greedy algorithm efficiency.
Common Use Cases:
Finding optimal solutions (min/max).
Counting total solutions.
Historical Note: Invented by Richard Bellman in the 1950s to obscure the nature of mathematical research due to a fear of the term 'research' by the Secretary of Defense.
Understanding Dynamic Programming
Key Concept: Identify and solve all subproblems.
Challenge: Identifying what problems to solve can be difficult.
Learning Curve: The more problems solved, the better one becomes at recognizing subproblems.
Fibonacci Problem
Objective: Write a function to return the nth Fibonacci number.
Fibonacci Sequence: Starts with 1, 1; each subsequent number is the sum of the previous two.
Naive Recursive Solution:
Base cases: fib(1) and fib(2) both return 1.
Recursive case: fib(n) = fib(n-1) + fib(n-2).
Issue with Naive Approach: Very slow for large n (e.g., fib(50)).
Time Complexity of Naive Solution
Running Time: T(n) = T(n-1) + T(n-2) + O(1).
Complexity: Exponential time complexity, approximately O(2^n).
Memoization Solution
Concept: Store previously computed Fibonacci numbers to avoid redundant calculations.
Implementation: Use a dictionary (memo) to store computed values.
Complexity of Memoized Solution: O(n) because each number is computed only once.
Key Idea: Remember solutions and reuse them to solve larger problems.
Bottom-Up Approach
Alternative to Memoization: Compute solutions for all subproblems first, saving memory by only keeping necessary values.
Dependency Order: Solve subproblems in topological order to respect dependencies.
Coin Change Problem
Objective: Find the minimum number of coins to make a target amount.
Example: Change for 734 cents using euro coins.
Greedy Approach: Works in some cases (euro coins) but not in general (e.g., coins {1, 4, 5} for target 13).
Recursive Formulation
Base Case: Minimum coins for amount 0 = 0.
Recursive Relation: Explore all possible coin choices to find the best solution.
Time Complexity: O(M
K) where M is the target amount and K is the number of coin types.
Bottom-Up Coin Change Solution
Iterate: Store solutions for each sum up to M using available coins.
Counting Change Problem
Objective: Find how many ways can we form a given sum using coins.
Base Case: One way to form zero sum (using no coins).
Recursive Relation: Sum solutions across all subproblems.
Rabbit Grid Problem
Objective: Count the ways a rabbit can move in an N x M grid (only down or right).
Base Case: One way to reach the bottom right corner from the last row or column.
Recursive Solution: Sum paths moving down and right.
Key Takeaways
Start by defining subproblems and their base cases.
Visualize the problem for better understanding.
Future videos will cover more complex dynamic programming problems.
Encourage engagement: Like the video and subscribe for updates.