四刷 06/2022
Version #1 1D dp bottom up - not good
这个用了两个dp array交换
后来发现其实一个array就可以了
因为每次都是向后看
所以即使覆盖了自己也没关系
三角形 N^2个nodes，N-> length of the bottom layer
Time O(N^2)
Space O(N)
但是如果traverse所有的path应该是2^N paths，因为每次都可以向左走或者向右走
*
* *
* * *
Runtime: 2 ms, faster than 92.99% of Java online submissions for Triangle.
Memory Usage: 42.2 MB, less than 80.12% of Java online submissions for Triangle.
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int lastIndex = triangle.size() - 1;
List<Integer> bottom = triangle.get(lastIndex);
int[][] dp = new int[2][bottom.size()];
for (int i = 0; i < bottom.size(); i++) {
dp[lastIndex % 2][i] = bottom.get(i);
}
for (int index = triangle.size() - 2; index >= 0; index--) {
List<Integer> layer = triangle.get(index);
for (int i = 0; i < layer.size(); i++) {
dp[index % 2][i] = Math.min(dp[(index + 1) % 2][i], dp[(index + 1) % 2][i + 1]) + layer.get(i);
}
}
return dp[0][0];
}
}
Version #2 1D dp bottom up -> optimal
Runtime: 2 ms, faster than 92.99% of Java online submissions for Triangle.
Memory Usage: 44.3 MB, less than 30.14% of Java online submissions for Triangle.
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
List<Integer> bottom = triangle.get(triangle.size() - 1);
int[] dp = new int[bottom.size()];
for (int i = 0; i < bottom.size(); i++) {
dp[i] = bottom.get(i);
}
for (int index = triangle.size() - 2; index >= 0; index--) {
List<Integer> layer = triangle.get(index);
for (int i = 0; i < layer.size(); i++) {
dp[i] = Math.min(dp[i], dp[i + 1]) + layer.get(i);
}
}
return dp[0];
}
}
1D dp array -> top to bottom
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
站在当前level的当前Node, 可能有两种路径可以走向当前Node1/上一层的i; 2/上一层的i-1
譬如5可以从3走来，也可以从4走来，所以dp[5] = 5 + Math.min(3, 4)
每一层的首尾都是corner case, 若i = 0 则没有 dp[i - 1], 若i = size - 1 则没有dp[i],但尾的情况不需要单独考虑因为dp[i]初始化为Integer.MAX_VALUE
所以Math.min(dp[i - 1], dp[i]) always select dp[i - 1]
Time O(n)
Space O(n) -> length of the leaf level
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// i, i-1
// dp[i] -> minimum path to get to current cell
// dp[i] = cell + Math.min(dp[i+1], dp[i])
if (triangle == null || triangle.size() == 0) {
return 0;
}
int depth = triangle.size();
int[] dp = new int[triangle.get(depth - 1).size()];
dp[0] = triangle.get(0).get(0);
for (int i = 1; i < depth; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 1; i < depth; i++) {
List<Integer> list = triangle.get(i);
for (int j = list.size() - 1; j >= 0; j--) {
if (j == 0) {
dp[j] = list.get(j) + dp[j];
} else {
dp[j] = list.get(j) + Math.min(dp[j - 1], dp[j]);
}
}
}
int min = dp[0];
for (int sum : dp) {
min = Math.min(min, sum);
}
return min;
}
}
这个是传统的dp的顺序
bottom to top
Start from the most detailed subproblem
95.75 %
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
int[] dp = new int[triangle.get(triangle.size() - 1).size()];
for (int row = triangle.size() - 1; row >= 0; row--) {
List<Integer> level = triangle.get(row);
for (int col = 0; col < level.size(); col++) {
if (row == triangle.size() - 1) {
dp[col] = level.get(col);
} else {
dp[col] = level.get(col) + Math.min(dp[col + 1], dp[col]);
}
}
}
return dp[0];
}
}
Version #1 2D dp array
58.95 %
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null) return 0;
int rows = triangle.size();
if (rows == 0) return 0;
int cols = triangle.get(rows - 1).size();
int[][] dp = new int[rows][cols];
for (int y = 0; y < cols; y++) {
dp[rows - 1][y] = triangle.get(rows - 1).get(y);
//System.out.println(dp[rows - 1][y]);
}
for (int x = rows - 2; x >= 0; x--) {
for (int y = x; y >= 0; y--) {
dp[x][y] = triangle.get(x).get(y) + Math.min(dp[x + 1][y], dp[x + 1][y + 1]);
}
}
return dp[0][0];
}
}
Version #2 1D rolling dp array
二刷
96.78 %
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null) return 0;
int rows = triangle.size();
if (rows == 0) return 0;
int cols = triangle.get(rows - 1).size();
int[] dp = new int[cols];
for (int y = 0; y < cols; y++) {
dp[y] = triangle.get(rows - 1).get(y);
//System.out.println(dp[rows - 1][y]);
}
for (int x = rows - 2; x >= 0; x--) {
for (int y = 0; y <= x; y++) {
dp[y] = triangle.get(x).get(y) + Math.min(dp[y], dp[y + 1]);
}
}
return dp[0];
}
}
一刷
有一个简化代码的方法是
把dp size+1 然后不讨论 if (row == triangle.size() - 1)
也就是说把初始化省略
因为一开始dp array全是0
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) throw new IllegalArgumentException();
if (triangle.size() == 1) return triangle.get(0).get(0);
int[] dp = new int[triangle.size()];
//min path sum from bottom to curr layer
for(int row = triangle.size() - 1; row >= 0; row--) {
for (int col = 0; col <= row; col++) {
if (row == triangle.size() - 1) dp[col] = triangle.get(row).get(col);
else {
dp[col] = Math.min(dp[col], dp[col + 1]) + triangle.get(row).get(col);
}
}
}
return dp[0];
}
}
No comments:
Post a Comment