Search
Dynamic Programming Patterns
Last updated
Feb 1, 2023
# Dynamic Programming Patterns
https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns
# Minimum (Maximum) Path to Reach a Target
Statement
Give a target find min (max) cost/path/sum to reach the target.
Approach
Choose min (max) path among all possible paths before the current state, then add value for the current state.
1
| 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
1
2
3
4
5
| 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
1
2
3
4
5
6
7
8
9
| 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]
|
# Examples
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (i == 0 && j == 0) {
dp[i][j] = grid[i][j];
continue;
}
if (i == 0) {
dp[i][j] = dp[i][j-1] + grid[i][j];
} else if (j == 0) {
dp[i][j] = dp[i-1][j] + grid[i][j];
} else {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int[][] dp = new int[triangle.size()][triangle.get(triangle.size()-1).size()];
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[i][j] = dp[i-1][0] + triangle.get(i).get(j);
} else if (j == i) {
dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
} else {
dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
}
}
}
int ans = Integer.MAX_VALUE;
for (int v: dp[triangle.size()-1]) {
ans = Math.min(ans, v);
}
return ans;
}
}
|