力扣面试150 三角形最小路径和 DFS 记忆化搜索 DP 滚动数组优化DP
Problem: 120. 三角形最小路径和
👩🏫 甜姐题解
Code
class Solution {// 朴素DP// public int minimumTotal(List<List<Integer>> triangle) {// int n = triangle.size();// int[][] dp = new int[n+1][n+1];// for(int i = n-1; i >= 0; i--){// for(int j = 0; j <= i; j++){// dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);// }// }// return dp[0][0];// }// 滚动数组优化DPpublic int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size();int[] dp = new int[n+1];for(int i = n-1; i >= 0; i--){for(int j = 0; j <= i; j++){dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);}}return dp[0];}}