动态规划(1):三角形的最小路径和
创始人
2025-05-30 03:01:10

目录

1.分析

1.1当j == 0时

1.2当j == i时

1.3一般情况

2.题解

1.分析

120. 三角形最小路径和 - 力扣（Leetcode）

设F(i,j)是到达下标(i,j)的最小路径。

arr表示三角形数组。

起始状态:F(0,0)=arr[0][0];

此时有三种情况(三种转移状态):

1.1当j == 0时

F(i,j)=F(i-1,j)+arr[i][j];

1.2当j == i时

F(i,j)=F(i-1,j-1)+arr[i][j];

1.3一般情况

F(i,j)=min(F(i-1,j-1),F(i-1,j))+arr[i][j];

2.题解

知道每个下标的最小路径的情况下，只需要从最后一行中找到最小的那个数即是最短路径。

代码：

class Solution {
public:int minimumTotal(vector>& triangle) {int row=triangle.size();for(int i=1;i

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：最新消息“新金龙究竟是不是有挂”[详细教程]

下一篇：独家分享.衡阳跑胡子究竟有挂吗.(确实真的有挂)

相关内容

热门资讯

「玩家攻略」“新美猴王到底是有... 您好：新美猴王这款游戏可以开挂，确实是有挂的，需要了解加客服微信【8383742】很多玩家在这款游戏...
玩家实测“诸暨游戏开挂教程方法... 您好：诸暨游戏这款游戏可以开挂，确实是有挂的，需要了解加客服微信【3636476】很多玩家在这款游戏...
最新消息“九.游斗牛究竟有挂吗... 亲.九.游斗牛这款游戏是可以开挂的，确实是有挂的,通过添加客服【4830828】很多玩家在这款游戏中...
实测分享“518互游其实是有透... 您好：518互游这款游戏可以开挂，确实是有挂的，需要软件加微信【4194432】，很多玩家在518互...
重大通报“新蜜瓜斗牛到底真的有... 您好：新蜜瓜斗牛这款游戏可以开挂，确实是有挂的，需要软件加微信【4194432】，很多玩家在新蜜瓜斗...