动态规划解决 三角形最小路径和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        //dp[i][j]代表顶部到（i, j）的最小路径和
        int[][]dp = new int[len][len];
        //初始化边界条件
        dp[0][0] = triangle.get(0).get(0);
        //注意 i j的下标
        for(int i = 1; i < len; i++){
            for(int j = 0; j <= i; j++){
        //状态转移方程的三种情况
                if(j == 0){
                    dp[i][j] = dp[i - 1][0] + triangle.get(i).get(0);
                }else if(j == i){
                    dp[i][j] = dp[i -1][j - 1] + triangle.get(i).get(j);  
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j -1], dp[i -1][j]) + triangle.get(i).get(j);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for(int j = 0; j < len; j++){
            if(min > dp[len - 1][j]){
                min = dp[len -1][j];
            }
        }

        return min;

    }
}

最后

以上就是魁梧山水为你收集整理的动态规划解决 三角形最小路径和的全部内容，希望文章能够帮你解决动态规划解决 三角形最小路径和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。