120. 三角形最小路径和120. 三角形最小路径和题目题解class Solution { public int minimumTotal(ListListInteger triangle) { int[][] dp new int[triangle.size()1][triangle.size()1]; dp[0][0]triangle.get(0).get(0); //从最后一行开始递推 for(int itriangle.size()-1;i0;i--) { for(int j0;ji;j) { //当前行的最小路径和就是下一行的j,j1两个位置的最小值当前值 dp[i][j]Math.min(dp[i1][j],dp[i1][j1])triangle.get(i).get(j); } } return dp[0][0]; } }优化空间版class Solution { public int minimumTotal(ListListInteger triangle) { // int[][] dp new int[triangle.size()1][triangle.size()1]; int[] dp new int[triangle.size()1]; //从最后一行开始递推 for(int itriangle.size()-1;i0;i--) { for(int j0;ji;j) { //当前行的最小路径和就是下一行的j,j1两个位置的最小值当前值 dp[j]Math.min(dp[j],dp[j1])triangle.get(i).get(j); } } return dp[0]; } }