Problems based on the Dynamic Programming approach
- Introduction
- DP Patterns
- Problems
-
General, powerful algorithm design technique
-
Dynamic Programming was invented by a guy named Richard Bellman
-
We can solve problems by polynomial time using DP
-
Intended for optimization problems
- Like shortest paths, minimum-length path ( to find the best way to do something)
- Minimize or maximaze something (optimization problem)
-
DP => recursion + memoization
-
DP => subproblems + "reuse"
Fib(4)
/ \
Fib(3) Fib(2)
/ \ / \
Fib(2) Fib(1) Fib(1) Fib(0)
/ \
Fib(1) Fib(0)
| Fib(0) | Fib(1) | Fib(2) | Fib(3) | Fib(4) |
|---|
- F(0) = 0, F(1) = 1
- F(n) = F(n-1) + F(n-2) -> {for n >= 2}
- Example: Fibonacci(6)
| F(6) | F(5) | F(4) | F(3) | F(2) | F(1) | F(0) |
|---|
- We have 1 parameter which is the prevoius sum, hence it's 1-D memoization/cache
- Fibonacci Number
- Climbing Stairs
- Min Cost Climbing Stairs
- House Robber
- Maximum Alternating Subsequence Sum
- Approach:
- Use two recursive calls for finding F(n-1) and F(n-2)
- Add them to get F(n) and to store F(n) in an array (memoization)
- Use two recursive calls for taking 1 step and 2 steps
- Add both of the count and to store the distinct no. of count in an array (memoization)
- Example:
coins = [1, 2, 3] target = 5 - We can only use the coins 0 or 1 times (0/1 Knapsack)
- The goal of the problem is to sum up for the target value
- We have 2 parameters which are coins & target, hence it's 2-D memoization/cache
| \ | Target | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| Coins | 1 | T | |||||
| 2 | T | ||||||
| 3 | T |
- Example:
coins = [1, 2, 3] target = 5 - Similar to 0/1 Knapsack problem but the only difference is we can choose coins for infinte amount of times (Unbounded knapsack)
- The goal of the problem (coins example) is still the same where we need to sum up for the target value
- We have 2 parameters which are coins & target, hence it's 2-D memoization/cache
| \ | Target | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| Coins | 1 | T | |||||
| 2 | T | ||||||
| 3 | T |
- Example:
"abc" , "ace" - Subsequence is choice of characters stricly following order and not consecutive
- LCS have 2 parameters which are the given two strings, hence it's 2-D memoization/cache
- Base case is the end of the strings
| \ | a | b | c | |
|---|---|---|---|---|
| a | x | |||
| c | x | |||
| e | x | |||
| x | x | x | 0 |
- Longest Common Subsequence
- Longest Increasing Subsequence
- Edit Distance
- Distinct Subsequences
- Maximum Alternating Subsequence Sum
- Longest Palindromic Subsequence
- Example:
"racecar" - We can choose a substring like
"e"and expand outwards to check other substrings - Along the way we can store the result in an array (1-D memoization/cache)
- Similarly we can choose two characters
"ce"for even length palindromes