当前位置:网站首页>leetcode 120. 三角形最小路径和

leetcode 120. 三角形最小路径和

2022-06-11 15:17:00 失忆机器

 动态规划问题。dp数组,方程为dp[j][i] = Math.min(dp[j+1][i],dp[j+1][i+1]) + 当前value值。

java代码如下

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n  = triangle.size();
        int[][] dp  = new int[n+1][n+1];
        for(int j = n - 1; j >= 0; j--){
            for(int i = 0; i <= j; i++){
                dp[j][i] = Math.min(dp[j+1][i],dp[j+1][i+1]) + triangle.get(j).get(i);
            }
        }
        return dp[0][0];
    }
}

原网站

版权声明
本文为[失忆机器]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_44196561/article/details/125227620