120. 三角形最小路径和

待我称王封你为后i 2022-10-10 01:49 171阅读 0赞

> 给定一个三角形 triangle ，找出自顶向下的最小路径和。
> 
> 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
> 
> 示例 1：
> 
> 输入：triangle = \[\[2\],\[3,4\],\[6,5,7\],\[4,1,8,3\]\]  
> 输出：11  
> 解释：如下面简图所示：  
>    2  
>   3 4  
>  6 5 7  
> 4 1 8 3  
> 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。  
> 示例 2：
> 
> 输入：triangle = \[\[-10\]\]  
> 输出：-10

class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
    
                /**
                还是动态规划
                    dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];
                 */
                 int m=triangle.size();
                 int n=triangle.get(triangle.size()-1).size();
                 int [][]dp=new int[m+1][n+1];
                 for(int i=n-1;i>=0;i--){//控制行数
                 for(int j=0;j<=i;j++){//控制列数
                     dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);
                 }
                 }
                 return dp[0][0];
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode120:三角形最小路径和

英文题目： Given a triangle, find the minimum path sum from top to bottom. Each step you...

￡神魔★判官ぃ/ 2024年04月19日 07:55/ 0 赞/ 78 阅读

相关 LeetCode 120：三角形最小路径和

[链接][Link 1] 题目： ![在这里插入图片描述][f6dd349b35be46b98a276a4b37447f0c.png] 方法一：dp+memo 类

傷城~/ 2024年04月07日 14:38/ 0 赞/ 95 阅读

相关 LeetCode-120. 三角形最小路径和

目录题目思路动态规划(由上到下) 动态规划(由下到上) 题目来源 [120. 三角形最小路径和][120.] 题目思

た入场券/ 2024年03月24日 16:59/ 0 赞/ 61 阅读

相关 120. 三角形最小路径和

题目：[添加链接描述][Link 1] 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标

喜欢ヅ旅行/ 2023年02月26日 04:24/ 0 赞/ 57 阅读

相关 120. 三角形最小路径和

> 给定一个三角形 triangle ，找出自顶向下的最小路径和。 > > 每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者

待我称王封你为后i/ 2022年10月10日 01:49/ 0 赞/ 172 阅读

相关 leetcode120三角形最小路径和

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

拼搏现实的明天。/ 2022年09月05日 11:27/ 0 赞/ 197 阅读

相关 leetcode 120. 三角形最小路径和

【前言】 python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/

朱雀/ 2022年04月13日 09:50/ 0 赞/ 202 阅读

相关 LeetCode .120. 三角形最小路径和 - 详解

题目描述给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如，给定三角形： [

Dear 丶/ 2022年03月18日 04:14/ 0 赞/ 209 阅读

相关【Leetcode】120.三角形最小路径和

题目给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如，给定三角形： [ [2], [

旧城等待，/ 2022年01月20日 11:55/ 0 赞/ 256 阅读

相关 120.三角形最小路径和

//给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 // 相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标

￡神魔★判官ぃ/ 2021年06月22日 15:38/ 0 赞/ 403 阅读