GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — 三角形最小路径和-120 · Issue #80 · sl1673495/leetcode-javascript Open Labels Description给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。 例如，给定三角形： 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 说明： 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。 来源：力扣（LeetCode） 思路太久没做动态规划的题了，想了好久怎么去做 DP 的表，后来发现这题的 DP 解是相对比较暴力的，状态转移方程是： 也就是上一层的某个 那么先从最后一行开始求每一个下标所对应的最小路径，也就是最后一行每个下标本身的值，作为基础状态，然后向上面的行求解即可。 /** * @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] } 当然，由于每一行的求解只依赖于下一行的最优解，所以 /** * @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] } ActivityMetadataMetadataAssigneesLabelsProjectsMilestoneRelationshipsDevelopmentIssue actions |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |