Dynamic Programming error
Approach
This example
my solution:
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int row = triangle.size();
int col = triangle.get(row-1).size();
int[] dp = new int[col];
dp[0] = triangle.get(0).get(0);
for(int i=1; i<row;i++){
List<Integer> cur = triangle.get(i);
for(int j=0; j<cur.size; j++){
// correct ans is below
// for(int j = cur.size() - 1; j >= 0; j--){
if(j==0){
dp[0] = dp[0] + cur.get(j);
}
else if(j==cur.size()-1){
dp[j] = dp[j-1] +cur.get(j);
}
else{
dp[j] = Math.min(dp[j-1],dp[j]) + cur.get(j);
}
}
}
int min = Integer.MAX_VALUE;
for(int a:dp){
min = Math.min(min,a);
}
return min;
}
}
Why is mine wrong?
Btw bottom-top approach is better here
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// corner case
if(triangle == null || triangle.size() == 0) return 0;
// M[i] represents the min total from bottom to current position
// copy the last row in triangle to M
int m = triangle.size();
int n = triangle.get(m - 1).size();
int[] M = new int[n];
for(int i = 0; i < n; i++){
M[i] = triangle.get(m - 1).get(i);
}
// induction rule
// M[i] = min(M[i], M[i + 1]) + curVal
for(int i = n - 2; i >= 0; i--){
List<Integer> cur = triangle.get(i);
for(int j = 0; j < cur.size(); j++){
M[j] = Math.min(M[j], M[j + 1]) + cur.get(j);
}
}
return M[0];
}
}