知識點：倒敘的動態規劃
題目傳送

解法一：二維動態規劃【容易理解】

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size();if (n == 1) {return triangle.get(0).get(0);}// dp[i][j]:走到第i層第j個的最小路徑和int[][] dp = new int[n + 1][n + 1];// 初始化左右兩側的值for (int i = 1; i <= n; i++) {dp[i][1] = dp[i - 1][1] + triangle.get(i - 1).get(0);dp[i][i] = dp[i - 1][i - 1] + triangle.get(i - 1).get(i - 1);}// 遞推中間的值for (int i = 3; i <= n; i++) {for (int j = 2; j < i; j++) {dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i - 1).get(j - 1);}}// 尋找最后一行最小值int min = dp[n][1];for (int j = 2; j <= n; j++) {if (dp[n][j] < min) {min = dp[n][j];}}return min;}
}

解法二：動態規劃 + 空間優化

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size();// dp[j]:走到當前層第j個的最小路徑和int[] dp = new int[n];dp[0] = triangle.get(0).get(0);for (int i = 1; i < n; i++) {// 初始化第i行最后一個位置dp[i] = dp[i - 1] + triangle.get(i).get(i);// 滾動遞推第i行前面的位置, 【因為要用到上一行左邊的值，所以這里要倒序】for (int j = i - 1; j > 0; j--) {dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);}// 更新第i行第一個位置的路徑和dp[0] += triangle.get(i).get(0);}// 尋找最后一行最小值int min = dp[0];for (int j = 1; j < n; j++) {if (dp[j] < min) {min = dp[j];}}return min;}
}