网站响应速度验收,wordpress采集淘宝客,俄罗斯乌克兰最新消息,网站空间2G一年多少钱算法思想与代码详解
这段代码采用的是**动态规划#xff08;Dynamic Programming#xff09;**的思想#xff0c;用来解决“120. 三角形最小路径和”问题。动态规划通过将问题分解成更小的子问题#xff0c;并通过保存子问题的解来避免重复计算#xff0c;从而提高效率。…
算法思想与代码详解
这段代码采用的是**动态规划Dynamic Programming**的思想用来解决“120. 三角形最小路径和”问题。动态规划通过将问题分解成更小的子问题并通过保存子问题的解来避免重复计算从而提高效率。 算法核心思路 从底向上计算Bottom-Up Approach 因为我们要求从顶点到底边的最小路径和可以从底边开始逐步向上计算每一层的最优解。每个位置的最小路径和取决于当前值和下一层两个可能的相邻路径值中的较小者。 状态表示DP数组 使用一个一维数组 dp 来保存“从当前层到底边的最小路径和”。dp[j] 表示从当前层位置 j 到底边的最小路径和。 状态转移方程 对于某一层的节点 triangle[i][j]它的最小路径和为 [ dp[j] \min(dp[j], dp[j 1]) triangle[i][j] ]dp[j] 表示当前位置 j 往下的最小路径dp[j1] 表示下一个位置 j1 往下的最小路径。 最终结果 计算完成后dp[0] 即为从三角形顶点到底边的最小路径和。 代码解读
public int minimumTotal(ListListInteger triangle) {int n triangle.size(); // 三角形的层数int[] dp new int[n]; // 用一维数组保存动态规划结果// 初始化将 dp 数组赋值为最后一层的值for (int i 0; i n; i) {dp[i] triangle.get(n - 1).get(i);}// 从倒数第二层开始向上计算每层的最小路径和for (int i n - 2; i 0; i--) {for (int j 0; j i; j) {// 动态规划状态转移当前点的最小路径和dp[j] Math.min(dp[j], dp[j 1]) triangle.get(i).get(j);}}// 最终答案存储在 dp[0]return dp[0];
}运行流程
以输入 triangle [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] 为例 初始化 将最后一层 [4, 1, 8, 3] 赋值到 dp 数组中 [ dp [4, 1, 8, 3] ] 从倒数第二层开始计算 第 3 层 ([6, 5, 7]) ( dp[0] \min(4, 1) 6 7 )( dp[1] \min(1, 8) 5 6 )( dp[2] \min(8, 3) 7 10 ) 更新后 [ dp [7, 6, 10, 3] ] 第 2 层 ([3, 4]) ( dp[0] \min(7, 6) 3 9 )( dp[1] \min(6, 10) 4 10 ) 更新后 [ dp [9, 10, 10, 3] ] 第 1 层 ([2]) ( dp[0] \min(9, 10) 2 11 ) 更新后 [ dp [11, 10, 10, 3] ] 最终结果 返回 dp[0]即最小路径和为 11。 时间和空间复杂度 时间复杂度 外层循环从底层到顶层共 (n-1) 次。内层循环每层最多运行 (i1) 次整体为 (O(n^2))。总时间复杂度 (O(n^2))。 空间复杂度 使用了一个一维数组 dp大小为 (n)。总空间复杂度 (O(n))。 总结
这段代码通过动态规划的思想从底向上逐层计算路径和用一个一维数组优化了空间开销避免了重复计算具有较高的效率适用于求解此类逐层递归累加的问题。
java 实现
class Solution {public int minimumTotal(ListListInteger triangle) {int n triangle.size();int[] dp new int[n];for(int i 0; i n; i) {dp[i] triangle.get(n - 1).get(i);}for(int i n - 2; i 0; i--) { // i 自底向上for(int j 0; j i; j) { // j 对当前行从左到右遍历, 当 j i 时,该行的dp[i]值得以确定dp[j] Math.min(dp[j], dp[j 1]) triangle.get(i).get(j);}}return dp[0];}
}
