Dynamic Programming
Fibonacci
- Leetcode - 70. Climbing Stairs
- Leetcode - 509. Fibonacci Number
- Leetcode - 1137. N-th Tribonacci Number
Sequence
Jianzhi
- Leetcode - 198. House Robber
- Leetcode - 213. House Robber II
- Leetcode - 256. Paint House
- Leetcode - 926. Flip String to Monotone Increasing
- Leetcode - 873. Length of Longest Fibonacci Subsequence
- Leetcode - 132. Palindrome Partitioning II
Subsequence and Subarray
Overview
- Elements in a subsequence have to have the same order as in the original array, but does not need to be contiguous in the original array.
- Elements in a subarray must be contiguous in the original array.
- For example, [1, 3, 5] is a subsequence of [1, 2, 3, 4, 5], but not a subarray. [1, 2, 3] is a subarray.
Maximum Subarray
Description
- Given an integer array, find the subarray with the largest sum, and return its sum
Dynamic Programming
- Subproblem: The maximum sum of subarrays ends with nums[i]
- Recurrence relation: sum[i] = max(sum[i - 1] + nums[i], nums[i])
- Time complexity: O(N)
Exercise
- Leetcode - 53. Maximum Subarray
Longest Increasing Subsequence
Description
- Given an integer array, return the length of the longest strictly increasing subsequence
Dynamic Programming
- Subproblem: The length of the LIS of subarray nums[0..i]
- Recurrence relation: length[i] = maxj < i, nums[j] < nums[i] (length[j] + 1)
- Time complexity: O(N^2)
Exercise
- Leetcode - 300. Longest Increasing Subsequence
- Leetcode - 673. Number of Longest Increasing Subsequence
- Leetcode - 646. Maximum Length of Pair Chain
- Leetcode - 1218. Longest Arithmetic Subsequence of Given Difference
- Leetcode - 1027. Longest Arithmetic Subsequence
- Leetcode - 354. Russian Doll Envelopes
- Leetcode - 1964. Find the Longest Valid Obstacle Course at Each Position
Two Subsequences
Longest Common Subsequence
- Leetcode - 1143. Longest Common Subsequence
- Leetcode - 1035. Uncrossed Lines
Edit Distance
Jianzhi
- Leetcode - 115. Distinct Subsequences
0-1 Knapsack
Classical 0-1 Knapsack
Description
Given the weights and profits of N items, and a knapsack which has a capacity C Select items to put in the knapsack to get maximum profit Each item can only be selected once
Solution
- Subproblem: for the first i items, with capacity C, the maximum profit we can get dp[i][C]
- Relation: for the i-th item, if we do not take it, the max profit we get is dp[i-1][C] ; if we take it, the max profit we get is dp[i-1][j - weight[i]] + profit[i]. So the recurrence relation: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + profit[i])
- Base case: dp[i, 0] = 0, 0 <= i <= N
- Order: We can do either: first iterate through first 1..N item, then in the inner loop iterate though capacity 0..C; or first iterate through capacity 0..C, then in the inner loop iterate though first 1..C items. But with the first approach, we can use a 1-d array dp[C].
Subset Sum
Description
Given an integer array nums and an integer target.
Return whether a subset of the array sums to target
Solution
- This problem can be converted to a classical 0-1 knapsack problem, where the weight and profit of a item is the same. Then for a capacity C, the max possible profit can be obtained is C. So if the max profit is C (
target), then a subset of the array can sumstarget, and if less than C (target) then no. - We can also define subproblem on its own: for the first
iitems with a targetj, can a subset of the items sum toj. Then the recurrence relation is: dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
Exercises
- Leetcode - 416. Partition Equal Subset Sum
- Leetcode - 494. Target Sum link
- Leetcode - 1049. Last Stone Weight II # Mimum Subset Difference link
- Leetcode - 40. Combination Sum II # similar, but return the number of combinations instead of the combinations link
- Leetcode - 474. Ones and Zeroes # BONUS: Not in grokking, but useful link
Unbounded Knapsack
Classical Unbounded Knapsack
Description
Given the weights and profits of N items, and a knapsack which has a capacity C Select items to put in the knapsack to get maximum profit Each item can only be selected infinite times
Fewest number of items
- Leetcode - 322. Coin Change
Ways of adding items to a target
- Leetcode - 518. Coin Change II
Matrix
Jianzhi
- Leetcode - 62. Unique Path
- Leetcode - 64. Minimum Path Sum
- Leetcode - 120. Triangle
Best Time to Buy and Sell Stock
Buy and Sell One time
Solution
- For each selling price, the best buying price is the minimum price before the selling price. So we can iterate through the prices, and keep track of the
minPrice, encountered, and update themaxProfitadmaxProfit = max(maxProfit, price[i] - minPrice - Time complexity: O(n), Space complexity: O(1)
Exercise
- Leetcode - 121. Best Time to Buy and Sell Stock
Buy and Sell Multiple Times
Solution
- The best strategy is: buy at each valley, and sell at the next peak. Because if we don’t but at valley and sell at peak, selling at the nearest valley and buying at the nearest peak can always achieve a better profit. And if we don’t buy and sell at consecutive valleys and peaks, selling and buying at the valley and peak in between can always get a better profit.
- We can simply accumulate value when the prices climbs, and leave the profit as it is as the price drops.
- Time complexity: O(n), Space complexity: O(1)
Exercise
- Leetcode - 122. Best Time to Buy and Sell Stock II
Buy and Sell Multiple Times with Cooldown
Buy and Sell At Most Two Times
- Leetcode - 123. Best Time to Buy and Sell Stock III
Buy and Sell At Most K Times
- Leetcode - 188. Best Time to Buy and Sell Stock IV
TODO 剑指 Offer 动态规划
- 14 剪绳子 343. Integer Break