LeetCode 120:三角形最小路径和的两种解法(动态规划优化)

ops/2024/12/1 10:05:29/

题目链接:120. 三角形最小路径和

题目描述:

给定一个三角形triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标i,那么下一步可以移动到下一行的下标 ii + 1

示例 1:

输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:23 46 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

示例 2:

输入:triangle = [[-10]]
输出:-10

提示

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -10^4 <= triangle[i][j] <= 10^4

如图所示:
例子:
[[20],[30,40],[60,50,70],[40,10,80,30]]

在这里插入图片描述


dp_45">思路1:从上开始dp

分析:
在这里插入图片描述

class Solution {
public:int minimumTotal(vector<vector<int> > &triangle) {if(triangle.empty())    return 0;int row = triangle.size();vector<vector<int>> dp(row);for(size_t i =0;i<row;++i){dp[i].resize(triangle[i].size(),0);}//初始化dp[0][0] = triangle[0][0];//状态转移for(size_t i = 1;i<row;++i){for(size_t j = 0;j<=i;++j){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-1], dp[i-1][j] ) + triangle[i][j];}}}//最后一行int min_s = dp[row-1][0];for(size_t i = 1;i < dp[row-1].size();++i){min_s = min(dp[row-1][i],min_s);}return min_s;}
};

dp_89">思路2:从下向上dp,优化空间复杂度

思路1的时间复杂度为O(n^2),显然空间复杂度过高了,可以优化为O(n),思想如下:
在这里插入图片描述

class Solution {
public:int minimumTotal(vector<vector<int> > &triangle) {if(triangle.empty())    return 0;int row = triangle.size();vector<int> dp(triangle[row-1].size());//初始化for(size_t i = 0;i<dp.size();++i){dp[i] = triangle[row-1][i];}//状态转移for(int i = row-2;i>=0;--i){for(int j = 0;j<triangle[i].size();++j){dp[j] = triangle[i][j] + min(dp[j],dp[j+1]);}}//最后一行return dp[0];}
};

http://www.ppmy.cn/ops/138166.html

相关文章

SpringMVC-08-json

8. Json 8.1. 什么是Json JSON(JavaScript Object Notation, JS 对象标记) 是一种轻量级的数据交换格式&#xff0c;目前使用特别广泛。采用完全独立于编程语言的文本格式来存储和表示数据。简洁和清晰的层次结构使得 JSON 成为理想的数据交换语言。易于人阅读和编写&#xf…

02-Linux系统权限维持

02-Linux系统权限维持 一 创建账号 1 在/etc/passwd中创建root的特权用户 /etc/passwd中数据的格式 账号:密码:uid:gid:描述:家目录:shell解释器&#xff0c;我们可以在/etc/passwd文件中添加一个test账号&#xff0c;密码为password123&#xff08;密文advwtv/9yU5yQ&#…

网络安全概论——网络加密与密钥管理

一、网络加密的方式及实现 1、常见的加密算法 常见的密钥加密算法类型大体可以分为三类:对称加密、非对称加密、单向加密。 对称加密算法采用单密钥加密&#xff0c;在通信过程中&#xff0c;数据发送方将原始数据分割成固定大小的块&#xff0c;经过密钥和加密算法逐个加密…

【论文笔记】Towards Online Continuous Sign Language Recognition and Translation

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: Towards Online Continuou…

ASP.NET Core面试题汇总

1.如何在controller中注入service? 在configservices方法中配置这个service。 在controller的构造函数中&#xff0c;添加这个依赖注入。 2.ASP.NET Core 比 ASP.NET 更具优势的地方是什么&#xff1f; 跨平台&#xff0c;ASP.NET Core 可以运行在 Windows 、Linux 和 MAC 系统…

无人机:智能航点规划技术!

一、核心技术 环境感知技术 环境感知是智能航点规划的基础&#xff0c;通过传感器&#xff08;如雷达、摄像头、激光雷达等&#xff09;实时收集飞行环境的信息&#xff0c;包括地形、障碍物、天气等。 这些信息被用于构建飞行环境的数字模型&#xff0c;为后续的航点规划提…

Redis进行性能优化可以考虑的一些策略

选择合适的数据结构 根据实际的需求选择合适的数据结构&#xff0c;以高效地访问和存储多个属性。 比如如果你需要存储用户的多个属性&#xff0c;如用户名、邮箱等&#xff0c;使用哈希可以比使用多个字符串键值对更节省内存 避免大key/value 较大地key和value会占用更多的…

宠物领养平台构建:SpringBoot技术路线图

摘 要 如今社会上各行各业&#xff0c;都在用属于自己专用的软件来进行工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。互联网的发展&#xff0c;离不开一些新的技术&#xff0c;而新技术的产生往往是为了解决现有问题而产生的。针对于宠物领养…