给定一个正三角形数组，自顶到底分别有 1，2，3，4，5...，n 个元素，找出自顶向下的最小路径和。
每一步只能移动到下一行的相邻节点上，相邻节点指下行种下标与之相同或下标加一的两个节点。
数据范围：三角形数组行数满足 
，数组中的值都满足 
例如当输入[[2],[3,4],[6,5,7],[4,1,8,3]]时，对应的输出为11，
所选的路径如下图所示：
[编程题]三角形最小路径和
从下往上原地动态规划，将原始的triangle数组视为dp数组。dp[i][j]表示从最底层的三角形累加到triangle[i][j]时所得到的最小值，因此它的值应该为triangle[i][j]加上它正下方和右下方中小的那个，状态转移方程为：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型二维数组
* @return int整型
*/
public int minTrace (int[][] triangle) {
// write code here
int n = triangle.length;
for(int i = n - 2; i >= 0; i--){
int m = triangle[i].length;
for(int j = 0; j < m; j++){
triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
return triangle[0][0];
}
}
发表于 2021-12-17 10:24:08
回复(1)
从上往下动态规划，注意三角的左边只由上它的上一个状态推出，斜边只由其左上边推出。
初始状态：dp[0][0] = triangle[0][0];
左边：dp[i][0] = dp[i - 1][0] + triangle[i][0];
斜边：dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
其他：dp[i][j] = triangle[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]);
最后找出dp最小路径
int minTrace(vector<vector<int> >& triangle) {
// write code here
int n = triangle.size();
vector<vector<int> > dp(n, vector<int>(n));
dp[0][0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
for (int j = 0; j < triangle[i].size(); ++j) {
if (j == 0) {
dp[i][0] = dp[i - 1][0] + triangle[i][0];
}
else if (j == i) {
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
}
else {
dp[i][j] = triangle[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]);
}
}
}
int res = dp[n - 1][0];
for (int i = 1; i < n; ++i) {
res = min(res, dp[n - 1][i]);
}
return res;
}
发表于 2022-04-24 17:10:15
回复(0)
int minTrace(vector<vector<int>> &triangle) // 二维数组
{
// write code here
int m = triangle.size(); // 行数
vector<vector<int>> dp(m, vector<int>(m, 0)); // 创建二维数组容器，并初始化为0
dp[0][0] = triangle[0][0]; // 确定边界值 // 初始化起点
for (int i = 1; i < m; i++)
{
for (int j = 0; j <= i; j++)//二维数组的话一般都是两层for循环遍历所有数据
{
if (j == 0)//前两部判断都是为了确定边界值，因为只有一行或一列，所以不需要考虑边界值
dp[i][j] = dp[i - 1][j] + triangle[i][j];
else if (j == i)
dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
else
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
}
}
int res = 1e9;
for (int i = 0; i < m; i++)
{
res = min(res, dp[m - 1][i]);
}
return res;
}
发表于 2025-02-26 16:41:44
回复(0)
正常解法：自上而下构建dp数组, dp[i][j] 表示第 i 层选择元素为 triangle[i][j]
状态转移三种可能：
1. i 层第一个元素只能是正上方转移过来
2. i 层第 i 个元素只能是 i-1 层 i-1 个元素转移过来
3. 其他是 1,2 中两种可能取其小
最后遍历最后一层找到最小值即为全局最小值
public static int minTrace(int[][] triangle) {
// write code here
if (triangle.length == 1) return triangle[0][0];
// dp[i][j] 表示第 i 层选 triangle[i][j] 时的最小值
int[][] dp = new int[triangle.length][triangle.length];
dp[0][0] = triangle[0][0];
dp[1][0] = dp[0][0] + triangle[1][0];
dp[1][1] = dp[0][0] + triangle[1][1];
// 当第 i 层时, 纵坐标最多为 i
for (int i = 2; i < triangle.length; i++) {
// 不能记录某一层的最小值是因为当层数增加时，该最小值就不是全局最小值
for (int j = 0; j <= i; j++) {
// 第一个元素，则只能是正上方转移过来
if (j == 0) dp[i][j] = triangle[i][j] + dp[i - 1][0];
// 最后一个元素，只能是左上角转移过来
else if (j == i) dp[i][j] = triangle[i][j] + dp[i - 1][j - 1];
// 其余两种可能
else dp[i][j] = triangle[i][j] + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
}
}
// 从最后一层找到最终最小值
int res = Integer.MAX_VALUE;
for (int i = 0; i < dp[dp.length - 1].length; i++) {
res = Math.min(res, dp[dp.length - 1][i]);
}
return res;
}
发表于 2024-11-06 23:31:33
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型二维数组
* @return int整型
*/
public int minTrace (int[][] triangle) {
// write code here
//当处于triangle[i][j]位置时候，到达该位置的最小路径和为dp[i][j]；
int dp[][]=new int[triangle.length][triangle.length];
//初始化dp数组
dp[0][0]=triangle[0][0];
for(int i=1;i<triangle.length;i++){
for(int j=0;j<triangle[i].length;j++){
//当处于该行最左边
if(j==0){
dp[i][j]=dp[i-1][j]+triangle[i][j];
//当处于该行最右边
}else if(i==j){
dp[i][j]=dp[i-1][j-1]+triangle[i][j];
//当处于该行中间
}else{
dp[i][j]=Math.min(dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]);
}
}
}
//寻找最后一行最大值
int min=Integer.MAX_VALUE;
for(int i=0;i<triangle.length;i++){
if(dp[triangle.length-1][i]<min){
min=dp[triangle.length-1][i];
}
}
return min;
}
}
发表于 2023-05-17 11:25:53
回复(1)
int minTrace(vector<vector<int> >& triangle) {
int n = triangle.size();
for (int i = 1; i < n; ++i) {
for (int j = 0; j < triangle[i].size(); ++j) {
if (j == 0) triangle[i][j] += triangle[i - 1][j];
else if (j == triangle[i].size() - 1) triangle[i][j] += triangle[i - 1][j - 1];
else {
triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
}
}
}
int res = triangle[n - 1][0];
for (int i = 0; i < triangle[n - 1].size(); ++i) {
res = min(res, triangle[n - 1][i]);
}
}
发表于 2021-12-02 16:03:54
回复(1)
class Solution {
public:
void sol(vector<vector<int> >& tri, int i, int j, int& cur,
vector<int>& all_path) {
if (i == tri.size() - 1) {
all_path.push_back(cur);
return;
}
cur += (tri[i + 1][j]);
sol(tri, i + 1, j, cur, all_path);
cur -= (tri[i + 1][j]);
cur += (tri[i + 1][j + 1]);
sol(tri, i + 1, j + 1, cur, all_path);
cur -= (tri[i + 1][j + 1]);
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace(vector<vector<int> >& triangle) {
// write code here
int cur=0;
cur += (triangle[0][0]);
vector<int> all_path;
sol(triangle, 0, 0, cur, all_path);
// cout << "sum.size()=" << all_path.size();
sort(all_path.begin(), all_path.end());
return all_path.front();
}
};
请教大佬为什么会超内存呢
发表于 2025-05-16 16:32:16
回复(0)
from re import S
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param triangle int整型二维数组
# @return int整型
#
class Solution:
def minTrace(self , triangle: List[List[int]]) -> int:
# write code here
sum=triangle[0][0]
cue=triangle[0][0]
if len(triangle)==1:
sum=triangle[0][0]
elif len(triangle)==0:
return 0
else:
for i in range(len(triangle)-1):
index=triangle[i].index(cue)
left=triangle[i+1][index]
right=triangle[i+1][index+1]
cue=min(left,right)
sum=sum+cue
return sum
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param triangle int整型二维数组
# @return int整型
#
class Solution:
def minTrace(self , triangle: List[List[int]]) -> int:
# write code here
sum=triangle[0][0]
cue=triangle[0][0]
if len(triangle)==1:
sum=triangle[0][0]
elif len(triangle)==0:
return 0
else:
for i in range(len(triangle)-1):
index=triangle[i].index(cue)
left=triangle[i+1][index]
right=triangle[i+1][index+1]
cue=min(left,right)
sum=sum+cue
return sum
看看有什么问题
发表于 2024-12-08 12:09:42
回复(0)
int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {
int dp[201][200];
dp[0][0]=triangle[0][0];
for (int i=1; i<triangleRowLen; i++) {
dp[i][0]=dp[i-1][0]+triangle[i][0];
}
for (int i=1; i<triangleRowLen; i++) {
for (int j=1; j<triangleColLen[i]; j++) {
if (j==triangleColLen[i]-1) {
dp[i][j]=dp[i-1][j-1]+triangle[i][j];
}
else {
dp[i][j]=(dp[i-1][j-1]<dp[i-1][j]?dp[i-1][j-1]:dp[i-1][j])+triangle[i][j];
}
}
}
int min=dp[triangleRowLen-1][0];
for (int i=0; i<triangleColLen[triangleRowLen-1]; i++) {
if(dp[triangleRowLen-1][i]<min){
min=dp[triangleRowLen-1][i];
}
}
return min;
}
发表于 2024-11-29 19:38:52
回复(0)
下一层每个元素的最小值均由上一层每个元素的最小值得出，然后递归就行了
function minTrace( triangle ) {
// write code here
let results=[triangle[0][0]]
let len=triangle.length
for(let i=1;i<len;i++){
let res=[]
triangle[i].forEach((item,j)=>{
const stepLen=triangle[i].length-1
if(j===0){
res.push(results[0]+item)
}else if(j===stepLen){
const lastStepLen=results.length-1
res.push(results[lastStepLen]+item)
}else{
res.push(Math.min(results[j],results[j-1])+item)
}
})
results=res
}
return Math.min(...results)
}
发表于 2024-11-03 13:19:22
回复(0)
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace(vector<vector<int> >& triangle) {
// write code here
// 总行数
int n=triangle.size();
for(int i=n-2;i>=0;i--){
for(int j=triangle[i].size()-1;j>=0;j--){
triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1]);
}
}
return triangle[0][0];
}
};
发表于 2024-08-29 22:03:07
回复(1)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型二维数组
* @param triangleRowLen int triangle数组行数
* @param triangleColLen int* triangle数组列数
* @return int整型
*/
int minTrace(int** triangle, int triangleRowLen, int* triangleColLen ) {
int dp[201][200] = {0};
int min=0;
dp[0][0] = triangle[0][0];
//先记录整个第一列的dp值
for(int i=1; i<triangleRowLen; i++)
dp[i][0] = dp[i-1][0] + triangle[i][0];
//然后每一个数都是起点到该店的最小路径，为上一个或前一个的最小路径加上自己
for(int i=1; i<triangleRowLen; i++)
{
for(int j=1; j<(triangleColLen[triangleRowLen-1]); j++)
{
if(j == triangleColLen[i]-1)
{
dp[i][j] = dp[i-1][j-1]+triangle[i][j];
continue;
}
min = dp[i-1][j]<dp[i-1][j-1]?dp[i-1][j]:dp[i-1][j-1];
dp[i][j] = min+triangle[i][j];
}
}
min = dp[triangleRowLen-1][0];
for(int j=0; j<(triangleColLen[triangleRowLen-1]); j++)
{
if(dp[triangleRowLen-1][j]<min)
min = dp[triangleRowLen-1][j];
}
return min;
// write code here
}
发表于 2024-08-19 14:56:58
回复(0)
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param triangle int整型二维数组 # @return int整型 # class Solution: def minTrace(self , triangle: List[List[int]]) -> int: # write code here dp = triangle.copy() for i in range(1, len(triangle)): for j in range(len(triangle[i])): if j == len(triangle[i]) - 1: dp[i][j] = dp[i-1][j-1] + triangle[i][j] elif j == 0: dp[i][j] = dp[i-1][j] + triangle[i][j] else: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] return min(dp[-1])
编辑于 2024-04-23 22:08:57
回复(0)
#include <climits>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace(vector<vector<int> >& triangle) {
// write code here
int n = triangle.size();
vector<int> dp(n, INT_MAX);
dp[0] = triangle[0][0];
for(int i=1; i<n; i++){
for(int j=i; j>0; j--){
dp[j] = min(dp[j],dp[j-1])+triangle[i][j];
}
dp[0] = dp[0]+triangle[i][0];
}
int res = INT_MAX;
for(int v : dp){
if(v<res) res = v;
}
return res;
}
};
编辑于 2023-12-27 16:11:15
回复(0)
#include <climits>
class Solution
{
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace(vector<vector<int> >& triangle)
{
int m = triangle.size();
vector<vector<int>> dp(m + 1, vector<int>(m + 1, INT_MAX));
dp[0][0] = dp[0][1] = 0;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= i; j++)
{
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i - 1][j - 1];
}
}
int ret = INT_MAX;
for (int i = 1; i <= m; i++)
{
ret = min(ret, dp[m][i]);
}
return ret;
}
};
发表于 2023-07-26 17:18:48
回复(0)
#include <algorithm>
class Solution {
public:
int minTrace(vector<vector<int> >& triangle) {
vector<vector<int>> minPathSum(triangle);
int row=triangle.size();
//从最后一行开始向上推导
for(int i=row-2;i>=0;--i)
{
for(int j=0;j<=i;++j)
{
minPathSum[i][j]=min(minPathSum[i+1][j+1],minPathSum[i+1][j])+triangle[i][j];
}
}
return minPathSum[0][0];
}
};
发表于 2023-05-22 19:56:00
回复(0)
class Solution: def minTrace(self , triangle: List[List[int]]) -> int: # 定义dp[i][j]为从下往上到第[i,j]个元素时的最小路径和 # 最后结果为dp[0][0] # dp转移方程为: dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j] # 初始状态: dp[m-1][j] = triangle[m-1][j] m, n = len(triangle), len(triangle[-1]) dp = [[0 for _ in range(n)] for _ in range(m)] for j in range(n): dp[m-1][j] = triangle[m-1][j] for i in range(m-2, -1, -1): for j in range(i+1): dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j] return dp[0][0]
发表于 2023-03-16 16:00:44
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型二维数组
* @param triangleRowLen int triangle数组行数
* @param triangleColLen int* triangle数组列数
* @return int整型
*/
int min(int a,int b)
{
return a<b?a:b;
}//取a,b中最小值
int minTrace(int** triangle, int triangleRowLen, int* triangleColLen )
{
for(int row=triangleRowLen-2;row>=0;row--)//从倒数第二行开始，从0开始记
{
for(int col=0;col<=row;col++)
{
triangle[row][col]+=min(triangle[row+1][col],triangle[row+1][col+1]);
}//triangle[row][col]表示从triangle[row][col]开始到最后一行中一个数总和中的最小和
}
return triangle[0][0];
}
/* 例如
2 从倒数第二行第一个数6开始,triangle[2][0]=6+min{4,1}，因为4<1，所以triangle[2][0]=7
3 4 以此类推 triangle[2][1]=6,triangle[2][2]=10
6 5 7
4 1 8 3 上升一行row-1,triangle[1][0]=3+min(triangle[2][0],triangle[2][1]),因为6<10,所以triangle[1][0]=9,triangle[1][1]=10,
上升一行row-1,triangle[0][0]=2+triangle[1][0]=11
*/
发表于 2023-01-10 17:48:48
回复(0)
没看清题目以为相邻节点包括下行中下标减一的节点，写了一堆代码判断临界值，检查半天代码，原来审题就出问题了
using System;
using System.Collections.Generic;
class Solution
{
public int minTrace(List<List<int>> triangle)
{
// f[y][x]表示到点(x, y)的最短路径长度
// f[y][x] = triangle[y][x] + min(f[y - 1][x - 1]+ f[y - 1][x])
List<List<int>> dp = triangle;
for (int y = 1; y < dp.Count; ++y)
{
dp[y][0] += dp[y - 1][0];
for (int x = 1; x < dp[y].Count - 1; ++x)
dp[y][x] += Math.Min(dp[y - 1][x - 1], dp[y - 1][x]);
dp[y][dp[y].Count - 1] += dp[y - 1][dp[y].Count - 2];
}
int minDist = dp[dp.Count - 1][0];
for (int x = 1; x < dp[dp.Count - 1].Count; ++x)
minDist = Math.Min(minDist, dp[dp.Count - 1][x]);
return minDist;
}
}
发表于 2023-01-08 16:54:59
回复(0)
问题信息
难度：
26条回答
67收藏
3536浏览
通过挑战的用户
查看代码-
2022-09-16 19:20:14 -
2022-09-16 12:57:58 -
2022-09-15 19:11:45 -
2022-09-15 13:35:46 -
2022-09-15 11:06:03
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
