Open AmelloAster opened 4 years ago
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如,给定三角形:
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
var minimumTotal = function (triangle) { for (let i = triangle.length - 1; i > 0; i--) { for (let j = 0; j < triangle[i].length - 1; j++) { triangle[i - 1][j] = Math.min( triangle[i - 1][j] + triangle[i][j], triangle[i - 1][j] + triangle[i][j + 1] ) } } return triangle[0][0] }
将三角形倒转 计算当前一排元素和下一排相邻元素之和的最小值 然后依次往上累加 最后返回三角形顶端的元素
显示详情 执行用时: 76 ms, 在所有 JavaScript 提交中击败了46.61%的用户 内存消耗: 36.1 MB, 在所有 JavaScript 提交中击败了50.00%的用户
120. 三角形最小路径和
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如,给定三角形:
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
解题代码
解题思路
解题效率