Open sl1673495 opened 4 years ago
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如,给定三角形:
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
说明:
如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/triangle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
太久没做动态规划的题了,想了好久怎么去做 DP 的表,后来发现这题的 DP 解是相对比较暴力的,状态转移方程是:
dp[level][index] = min( indexVal + dp[level + 1][index], indexVal + dp[level + 1][index + 1], )
也就是上一层的某个 index 的最小值是由下一层的两个相邻节点的最小值所决定的。
index
那么先从最后一行开始求每一个下标所对应的最小路径,也就是最后一行每个下标本身的值,作为基础状态,然后向上面的行求解即可。
/** * @param {number[][]} triangle * @return {number} */ let minimumTotal = function (triangle) { let dp = [] let n = triangle.length if (!n) { return 0 } dp[n - 1] = triangle[n - 1] for (let i = n - 2; i >= 0; i--) { dp[i] = [] let row = triangle[i] for (let j = 0; j < row.length; j++) { let curVal = row[j] dp[i][j] = Math.min( // 选择下一层同下标 curVal + dp[i + 1][j], // 选择下一层next下标 curVal + dp[i + 1][j + 1] ) } } return dp[0][0] }
当然,由于每一行的求解只依赖于下一行的最优解,所以 dp 数组可以压缩到只保存下一行的最优解:
dp
/** * @param {number[][]} triangle * @return {number} */ let minimumTotal = function (triangle) { let n = triangle.length if (!n) { return 0 } let prev = triangle[n - 1] for (let i = n - 2; i >= 0; i--) { let cur = [] let row = triangle[i] for (let j = 0; j < row.length; j++) { let curVal = row[j] cur[j] = Math.min( // 选择下一层同下标 curVal + prev[j], // 选择下一层next下标 curVal + prev[j + 1] ) } prev = cur } return prev[0] }
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如,给定三角形:
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
说明:
如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/triangle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
太久没做动态规划的题了,想了好久怎么去做 DP 的表,后来发现这题的 DP 解是相对比较暴力的,状态转移方程是:
也就是上一层的某个
index
的最小值是由下一层的两个相邻节点的最小值所决定的。那么先从最后一行开始求每一个下标所对应的最小路径,也就是最后一行每个下标本身的值,作为基础状态,然后向上面的行求解即可。
当然,由于每一行的求解只依赖于下一行的最优解,所以
dp
数组可以压缩到只保存下一行的最优解: