Buckets:
| tags: | |
| - notes | |
| - dynamic-programming | |
| - patterns | |
| # Patterns | |
| 1. [[#Minimum (Maximum) Path to Reach a Target]] | |
| 2. [[#Distinct Ways]] | |
| 3. [[#Merging Intervals]] | |
| 4. [[#DP on Strings]] | |
| 5. [[#Decision Making]] | |
| ## Minimum (Maximum) Path to Reach a Target | |
| Problem list: https://leetcode.com/problem-list/55ac4kuc/ | |
| Generate problem statement for this pattern | |
| ### Statement | |
| > [!Info] Given a target find minimum (maximum) cost / path / sum to reach the target. | |
| ### Approach | |
| > [!info] Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state. | |
| ```java | |
| routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i] | |
| ``` | |
| Generate optimal solutions for all values in the target and return the value for the target. | |
| ### Top-Down | |
| ```java | |
| for (int j = 0; j < ways.size(); ++j) { | |
| result = min(result, topDown(target - ways[j]) + cost/ path / sum); | |
| } | |
| return memo[/*state parameters*/] = result; | |
| ``` | |
| ### Bottom-Up | |
| ```java | |
| for (int i = 1; i <= target; ++i) { | |
| for (int j = 0; j < ways.size(); ++j) { | |
| if (ways[j] <= i) { | |
| dp[i] = min(dp[i], dp[i - ways[j]] + cost / path / sum) ; | |
| } | |
| } | |
| } | |
| return dp[target] | |
| ``` | |
| ### Similar Problems | |
| [746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/) `Easy` | |
| ## Distinct Ways | |
| ## Merging Intervals | |
| ## DP on Strings | |
| ## Decision Making | |
Xet Storage Details
- Size:
- 1.39 kB
- Xet hash:
- 674e1ddae6bcb4e07c0b1e0e00258e36e9a100a43a3cea174bbe4fe35198fd45
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.