网络异常，图片无法展示
|
「这是我参与2022首次更文挑战的第33天，活动详情查看：2022首次更文挑战」
给定一个三角形 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 <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
进阶：
- 你可以只使用
O(n)的额外空间（n为三角形的总行数）来解决这个问题吗？
解题思路
本题要我们求最小的路径和，也就是求最值问题，而且这个结果可以通过一层一层推导得到，这熟悉的性质，这不就是一道动态规划题嘛！😎
激动的心，颤抖的手，掏出动归三板斧！
- 状态定义：本题中影响最小路径和结果的有两个因素，一个是当前所在行数，一个数字在当前行的位置，所以我们可以定义二维 dp
dp[i][j]，表示第 i 行下标 j 位置的最小路径和。 - 转移方程：本题明确给出移动只能在相邻的结点上，那么以示例1为例，3 只能从 2 过来，5 只能从 3 或者 4 过来，1 只能从 6 或者 5 过来，又因为我们要求一个最短路径和，所以当有两个选择的时候，我们应该选择路径和更小的那个点作为前面的路径，所以可以推导出：
dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]。 - 接下来就是基于状态定义和转移方程编写代码了！
代码实现
var minimumTotal = function(triangle) { // 获取三角形高度 const len = triangle.length, // 初始化 dp dp = Array(len) for(let i = 0;i<len;i++){ dp[i] = [] } dp[0][0] = triangle[0][0] // 遍历每一层，推导 dp for(let i = 1;i<len;i++){ // 获取当前层的长度 const n = triangle[i].length; for(let j = 0;j<n;j++){ // 因为 j = 0 时没有上一层的 j-1，所以特殊处理 if(j === 0) dp[i][0] = dp[i-1][0]+triangle[i][0] // 因为 j 等于 n-1 的时候没有上一层的 j，所以特殊处理 else if(j===n-1) dp[i][j] = dp[i-1][j-1]+triangle[i][j] else dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j] } } // 返回最后一层 dp 中的最小值 return Math.min(...dp[len-1]) }; 复制代码
优化空间复杂度
var minimumTotal = function(triangle) { // 获取三角形高度 const len = triangle.length, // 初始化 dp dp = Array(len); dp[0] = triangle[0][0] // 遍历每一层，推导 dp for(let i = 1;i<len;i++){ // 获取当前层的长度 const n = triangle[i].length; // 因为当前一层的 j 依赖于上一层的 j 和 j-1，所以需要从后向前的推导每一层 dp for(let j = n-1;j>=0;j--){ // 因为 j = 0 时没有上一层的 j-1，所以特殊处理 if(j===0) dp[j] += triangle[i][j] // 因为 j 等于 n-1 的时候没有上一层的 j，所以特殊处理 else if(j===n-1) dp[j] = dp[j-1]+triangle[i][j] else dp[j] = Math.min(dp[j-1],dp[j])+triangle[i][j] } } // 返回最后一层 dp 中的最小值 return Math.min(...dp) }; 复制代码
至此我们就完成了 leetcode-120-三角形最小路径和
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
