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 |
- Pattern: Unbounded Knapsack
- Description: Given a rod of length
nand an array of prices for each length, determine the maximum value obtainable by cutting up the rod and selling the pieces. You can cut the rod in as many pieces as you want, and you can use each length multiple times (hence, unbounded). - State:
dp[n]= max value for rod of lengthn - Transition: For each possible cut
i(from 1 to n):dp[n] = max(dp[n], price[i-1] + dp[n-i])
- Base case:
dp[0] = 0 - Why Unbounded? You can use each cut length as many times as you want, just like coins in the coin change problem.
- 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