AlgoViz Lab交互式算法学习
Algorithms first

三角形最小路径和 · 交互式算法学习

求自顶向下相邻移动的最小路径和。

#120 · 多维动态规划

三角形最小路径和

Triangle

测试用例triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
状态表3 个关键状态
步骤 1dp 初始化为底层 [4,1,8,3]。base
00
2
1
3
2
4
3
6
4
5
5
7
6
4
7
1
8
8
9
3
当前状态转移来源
推荐

自底向上一维 DP

时间 O(n²)空间 O(n)

从倒数第二层开始，每格加下层相邻两个最小值。

1function minimumTotal(t) {2  const dp = [...t.at(-1)];3  for (let r = t.length - 2; r >= 0; r--)4    for (let c = 0; c <= r; c++) dp[c] = t[r][c] + Math.min(dp[c], dp[c + 1]);5  return dp[0];6}
多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Solution {2    public int minimumTotal(List<List<Integer>> triangle) {3        int n = triangle.size();4        int[][] f = new int[n + 1][n + 1];5        for (int i = n - 1; i >= 0; --i) {6            for (int j = 0; j <= i; ++j) {7                f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle.get(i).get(j);8            }9        }10        return f[0][0];11    }12}
交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。
动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。
适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。
AlgoViz Lab

三角形最小路径和 · 解法对比

AlgoViz Lab

求自顶向下相邻移动的最小路径和。

测试用例
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
题目分类
多维动态规划
解法对比
2
方案 1

递归枚举左右路径

每层可走左下或右下，递归取较小分支。

时间
O(2^n)
空间
O(n)
方案 2

自底向上一维 DP

从倒数第二层开始，每格加下层相邻两个最小值。

时间
O(n²)
空间
O(n)