三角形最小路径和

思路

动态规划

dp[m][n] = min(dp[m - 1][n - 1], dp[m - 1][n]) + tri[m][n]; (m > 0, n > 0)

缩减为一维的

dp[n] = min(dp[n], dp[n - 1]) + tri[m][n]; 

代码

二维

import java.util.Arrays;
import java.util.List;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        //初始化
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        dp[0][0] = triangle.get(0).get(0);
        for(int i = 1; i < n; i++){
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for(int j = 1; j < i + 1; j++){
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
        }
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            res = Math.min(res, dp[n - 1][i]);
        }
        return res;
    }
}

一维

import java.util.Arrays;
import java.util.List;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[]dp = new int[n];
        //初始化
        for(int i = 0; i < n; i++){
            dp[i] = Integer.MAX_VALUE;
        }

        dp[0] = triangle.get(0).get(0);
        for(int i = 1; i < n; i++){
           for(int j = i; j > 0; j--){
               dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);
           }
           dp[0] += triangle.get(i).get(0);
        }
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            res = Math.min(res, dp[i]);
        }
        return res;
    }
}