三角形最小路径和( LeetCode 120 )

一、题目描述

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 三角形最小路径和( LeetCode 120 ):https://leetcode-cn.com/problems/triangle/
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {

        // triangle 是个二维数组
        // 先获取 triangle 的层数,即一维数组的个数
        int n  = triangle.size();

        // 设置一个一维数组,动态的更新每一层中当前节点对应的最短路径
        int[] dp = new int[ n + 1 ];

        // 从最后一层开始计算节点的最短路径,直到顶层 0 层为止
        for (int i = n - 1 ; i >= 0 ; i-- ){
            // dp 中存储的是前 i 个位置存储的是到达第 i 层各个节点的最小路径和
            // 从每一层的第 0 个位置开始
            for(int j = 0 ; j <= i ; j++){
                // dp[j] 表示第 i 层中第 j 个节点的最小路径和
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j],dp[j+1]);
            }
        }

        // 返回结果
        return dp[0];

    }
}

2、C++ 代码

3、Python 代码

四、动画理解(没有声音)

隐藏内容
  • 普通用户购买价格:不可购买
  • 会员用户购买价格:999积分
  • 永久会员用户购买价格:免费推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注