LeetCode刷题记录：（15）三角形最小路径和

知识点：倒叙的动态规划
题目传送

解法一：二维动态规划【容易理解】

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;}
}