Buckets:
metadata
tags:
- notes
- dynamic-programming
- patterns
Patterns
- [[#Minimum (Maximum) Path to Reach a Target]]
- [[#Distinct Ways]]
- [[#Merging Intervals]]
- [[#DP on Strings]]
- [[#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.
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
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
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 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.