public int minimumTotal(List<List<Integer>> triangle) {
int[] A = new int[triangle.size()+1];
for(int i=triangle.size()1;i>=0;i){
for(int j=0;j<triangle.get(i).size();j++){
A[j] = Math.min(A[j],A[j+1])+triangle.get(i).get(j);
}
}
return A[0];
}
7 lines neat Java Solution


Javascript version:
var minimumTotal = function(triangle) { var A = new Array(triangle.length+1) A.fill(0) for(var i=triangle.length1;i>=0;i){ for(var j=0;j<triangle[i].length;j++){ A[j] = Math.min(A[j],A[j+1])+triangle[i][j]; } } return A[0]; };
Golang version:
func minimumTotal(triangle [][]int) int { A:=make([]int, len(triangle) + 1) for k, _ :=range A { A[k] = 0 } for i:=len(triangle)1; i>=0; i { for j:=0; j < len(triangle[i]); j++ { A[j] = min(A[j], A[j+1]) + triangle[i][j] } } return A[0] } func min(a int, b int) int { if a > b { return b } else { return a } }

DP from top to bottom:
public int minimumTotal(List<List<Integer>> triangle) { int m = triangle.size(); if (m == 0) return 0; int n = triangle.get(m  1).size(); if (n == 0) return 0; int[] dp = new int[m]; dp[0] = triangle.get(0).get(0); for (int i = 1; i < m; i++) { int l = triangle.get(i).size(); for (int k = l  1; k >= 0; k) { int curr = Math.min((k < l  1 ? dp[k] : Integer.MAX_VALUE), (k >= 1 ? dp[k  1]: Integer.MAX_VALUE)) + triangle.get(i).get(k); dp[k] = curr; } } int min = Integer.MAX_VALUE; for (int k = 0; k < n; k++) { min = Math.min(min, dp[k]); } return min; }

@ihaveayaya , for your toptobottom solution, it's better to make the inner
for
loop traverse from back to front, which will make it simpler.

@binz Thanks for pointing out. I made a few changes to make the code a little bit simpler. If you think there is still room to optimize, please let me know.