重庆网站线上推广,网站开发的可行性研究报告,注册网址查询,wordpress 增加小工具栏#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 动态规划 求解思路 实现代码 运行结果 共勉 题目链接
120. 三角形最小路径和
⛲ 题目描述
给定一个三角形 triangle 找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 1 的两个结点。也就是说如果正位于当前行的下标 i 那么下一步可以移动到下一行的下标 i 或 i 1 。
示例 1
输入triangle [[2],[3,4],[6,5,7],[4,1,8,3]] 输出11 解释如下面简图所示 2 3 4 6 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 -104 triangle[i][j] 104
进阶
你可以只使用 O(n) 的额外空间n 为三角形的总行数来解决这个问题吗 求解思路实现代码运行结果 ⚡ 动态规划 求解思路
dp[i][j] 表示从点 (i,j) 到底边的最小路径和。状态转移方程为 dp[i][j]min(dp[i1][j],dp[i1][j1])triangle[i][j]。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class Solution {public int[][] map;public int minimumTotal(ListListInteger triangle) {int n triangle.size();map new int[n 1][n 1];for (int i n - 1; i 0; i--) {for (int j triangle.get(i).size() - 1; j 0; j--) {map[i][j] Math.min(map[i 1][j], map[i 1][j 1]) triangle.get(i).get(j);}}return map[0][0];}
} 运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
