首页 > 试题广场 >

三角形

[编程题]三角形

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，

例如，给出的三角形如下：

[[20],[30,40],[60,50,70],[40,10,80,30]]

最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。

注意：

如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。

算法知识视频讲解

华科不平凡

发表于 2020-08-14 14:48:57

基本思想是自底向上，但是又可以细分为两种方法：空间复杂度O(n)，优点是无需修改输入空间复杂度O(1)，优点是无需辅助空间方法一 // // Created by jt on 2020/8/14. // #include <vector> using namespace std 展开全文

崔崔崔崔狗蛋啊

发表于 2022-01-05 22:54:06

import java.util.*; public class Solution { public int minimumTotal(ArrayList<ArrayList<In 展开全文

牛客689170892号

发表于 2022-06-23 08:41:48

设定F(i) i=1..n,是以第n行的第i个元素为结束的最短路径和假设第n-1行的F(1)..F(n-1)已经计算完毕，那么在计算第n行的F(1)..F(n)时，可以当i <=n-1时， F(i) = min(F(i-1), F(i)) +triangle[n-1][i-1] 展开全文

牛客139896114号

发表于 2022-04-05 20:26:48

CC31 三角形题目题解(4) 讨论(142) 排行中等通过率：27.90% 时间限制：1秒空间限制：32M 知识点动态规划描述给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，例如，给出的三角形如下： [[20],[30,40],[6 展开全文

ls.joshua

发表于 2020-04-21 09:26:25

不需要额外的空间，时间复杂度O(1/2 * N^2); class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int n = triangle.s 展开全文

打卡成功

发表于 2020-05-31 15:23:56

标题标题标题标题加粗斜体标题加粗斜体代码块行内代码import java.util.*;public class Solution { public int minimumTotal(ArrayList<ArrayList<integer>> t 展开全文

牛客Yhq

发表于 2023-03-16 09:06:59

// [20], // [30,40], // [60,50,70], // [40,10,80,30]] //状态：F（i，j）从（0，0）到（i，j）的路径和 //转移方程： // if(j==0):F(i,j)=F(i-1,j)+arr[i][j] // els 展开全文

问题信息

动态规划

难度：

144条回答 123收藏 31028浏览

查看代码