图解算法通识讲义经典套路
动态规划与状态转移推导
核心心智模型：大事化小，小事化了；记录历史子问题的最优解，推导当前决策的最优抉择。
核心交互式算法图解演练沙盒
动态规划模型
爬楼梯/斐波那契线性状态转移表推演
步骤 1 / 5
状态转移方程:dp[0] = 1, dp[1] = 1 (边界基准值)
空间滚动优化: 可压缩至 O(1)前驱子状态
1dp[0]
当前求值
1dp[1]
?dp[2]
?dp[3]
?dp[4]
?dp[5]
无后效性保证：当前状态仅由已确定的历史状态完全决定时间 O(N) · 空间 O(N) → O(1)
初始化边界状态：到达第 0 级台阶有 1 种方法，到达第 1 级台阶有 1 种方法。为后续推导打底。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 一维线性 DP 推导 | O(N) | O(N) | O(1) ~ O(N) | 单重循环历史回溯，常可用常数滚动变量优化。 |
| 二维网格 / 背包矩阵 | O(M * N) | O(M * N) | O(N) | 双重循环遍历状态矩阵，通过滚动行压缩空间。 |
template.java
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];解题核心心法提炼
- 状态定义的清晰度直接决定了转移方程的推导难度。
- 无后效性是能够使用 DP 的基本前提：一旦状态确定，后续演化不受之前决策路径的影响。
- 二维 DP 进行一维滚动压缩时，必须严格判断是依赖当前行（正序）还是依赖上一行历史状态（逆序）。
常见踩坑警示与避坑指南
- 初值初始化错误：求最小值时未初始化为无穷大，求最大值时未初始化为负数或0。
- 数组下标未留出 dummy 首项（例如 dp[n+1]），导致 i - 1 越界。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆