我要招人

去企业版

首页 > 试题广场 >

三角形最小路径和

[编程题]三角形最小路径和

热度指数：13752 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正三角形数组，自顶到底分别有 1，2，3，4，5...，n 个元素，找出自顶向下的最小路径和。

每一步只能移动到下一行的相邻节点上，相邻节点指下行种下标与之相同或下标加一的两个节点。

数据范围：三角形数组行数满足 $1 \le n \le 200 \$ ，数组中的值都满足 $|val| \le 10^4 \$

例如当输入[[2],[3,4],[6,5,7],[4,1,8,3]]时，对应的输出为11，

所选的路径如下图所示：

示例1

输入

[[10]]

输出

示例2

输入

[[2],[3,4],[6,5,7],[4,1,8,3]]

输出

说明

最小路径是 2 ， 3 ，5 ， 1

示例3

输入

[[1],[-1000,0]]

输出

-999

算法知识视频讲解

牛客768685351号

发表于 2022-03-10 18:42:06

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param triangle int整型vector<vector<>> 展开全文

红烧吹风机

发表于 2022-08-10 00:08:13

使用动态规划，从最后一个状态进行分解，设 dp[i][j] 表示在坐标（i，j）处能得到的最小总和，因为下一个点只能是当前点下方一个点，或者右下方一个点，那么 dp[i][j] 的表达式就是 dp[i][j] = min（ dp[i-1][j],dp[i-1][j-1] ） + c[i][j] 展开全文

酱橙~

发表于 2022-04-20 09:05:52

前端初学者，刚学动态规划的代码（较为繁琐） dp[i][j]表示以i,j位置的点为起点到达最低端的最小路径和。状态方程： dp[i][j] = min(triangle[i][j]+dp[i+1][j],triangle[i][j]+dp[i+1][j+1]) 边界条件：dp[n - 1][i] 展开全文

牛客826462999号

发表于 2022-04-25 23:56:11

利用一个数组dp来存储当前层的上一层元素，然后从前往后修改dp数组中的元素。 dp[j] = triangle[i][j] + min(dp[j],dp[j+1])，其中j表示当前层的第j个元素的下标。通过从后往前遍历每一层，就找到了每一个点的最小值的路径，最终遍历至一底层，最小值存储在dp[0] 展开全文

youxiwang

发表于 2022-02-01 13:04:49

从下往上dp f(i,j) = Min{f(i+1,j), f(i+1,j+1)} + v(i,j) O(n^2), O(n^2) TODO: 第二个for-loop倒着走可以空间优化至O(n) import java.util.*; public class Solution { p 展开全文

变成秃然的样子

发表于 2022-05-02 12:47:18

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param triangle int整型vector<vector<>> * @return int整型 */ int min 展开全文

天上掉下来SCI

发表于 2023-04-17 15:59:12

import traceback from sys import flags from itertools import count # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param triangle int整型二维数组 # @retur 展开全文