​LeetCode刷题实战120: 三角形最小路径和

共 1690字,需浏览 4分钟

 ·

2020-12-11 03:29

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 三角形最小路径和,我们先来看题面:
https://leetcode-cn.com/problems/triangle/

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

题意


给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

样例


解题


这道题目和之前的杨辉三角差不多,一看就是动态规划。 动态规划最主要的是确定状态表达式。而要求在 o(n)的空间复杂度来解决这个问题,最主要的是要想清楚,更新状态的时候,不破坏下一次计算需要用到的状态。 我们采用"bottom-up"的动态规划方法来解本题。

状态表达式为: dp[j] = min(dp[j], dp[j+1]) + triangle[j];


class Solution {
    public int minimumTotal(List> triangle) {
        int row = triangle.size();
        List res = new LinkedList<>(triangle.get(row - 1));
        for (int i = row - 2; i >= 0; i--) {
            List currentRow = triangle.get(i);
            for (int j = 0; j < currentRow.size(); j++) {
                res.set(j, Math.min(res.get(j), res.get(j + 1)) + currentRow.get(j));
            }
        }
        return res.get(0);
    }
}



好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-100题汇总,希望对你有点帮助!
LeetCode刷题实战101:对称二叉树
LeetCode刷题实战102:二叉树的层序遍历
LeetCode刷题实战103:二叉树的锯齿形层次遍历
LeetCode刷题实战104:二叉树的最大深度
LeetCode刷题实战105:从前序与中序遍历序列构造二叉树
LeetCode刷题实战106:从中序与后序遍历序列构造二叉树
LeetCode刷题实战107:二叉树的层次遍历 II
LeetCode刷题实战108:将有序数组转换为二叉搜索树
LeetCode刷题实战109:有序链表转换二叉搜索树
LeetCode刷题实战110:平衡二叉树
LeetCode刷题实战111:二叉树的最小深度
LeetCode刷题实战112:路径总和

LeetCode刷题实战113:路径总和 II

LeetCode刷题实战114:二叉树展开为链表

LeetCode刷题实战115:不同的子序列

LeetCode刷题实战116:填充每个节点的下一个右侧节点指针

LeetCode刷题实战117:填充每个节点的下一个右侧节点指针 II

LeetCode刷题实战118:杨辉三角

LeetCode刷题实战119: 杨辉三角 II


浏览 15
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报