DenCT/test-storage / DSA Notes /Dynamic Programming Notes.md
DenCT's picture
|
download
raw
1.39 kB
---
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.