动态规划

当你面对LeetCode上的六道股票买卖问题时，第一反应可能是：每道题都要单独学一种解法？这正是无数开发者的误区。实际上，这六道题可以用同一套状态转移方程统一解决——区别只在于边界条件的细微差异。 ...

每次你在终端输入 git diff，后台都在运行一个你可能刷过无数次的算法题——最长公共子序列。这不是巧合，而是计算机科学中最优雅的算法之一在实际工程中的自然落地。从版本控制到生物信息学，从拼写检查到数据压缩，LCS 找到了两个序列之间"最相似的部分"，而这个看似简单的问题背后，隐藏着动态规划的精髓。 ...

1962年，Michael Held和Richard Karp在《Journal of the Society for Industrial and Applied Mathematics》上发表了一篇论文，提出了用动态规划求解旅行商问题（TSP）的算法。这个算法的时间复杂度是 $O(n^2 \cdot 2^n)$——虽然仍然是指数级，但相比暴力枚举的 $O(n!)$，已经是一个巨大的飞跃。这个算法的核心思想，正是后来被称为"状态压缩动态规划"（Bitmask DP / State Compression DP）的开山之作。 ...

有 $n$ 个气球排成一排，每个气球上标有一个数字。当你戳破第 $i$ 个气球时，你会获得 nums[i-1] * nums[i] * nums[i+1] 枚硬币。如果相邻位置超出边界，则视为数字为 1 的虚拟气球。问题是：如何安排戳气球的顺序，才能获得最多的硬币？ ...

假设你需要从一个装满金条的宝库中选择带走一些金条，但背包容量有限。每根金条有重量和价值，如何在不超过背包容量的前提下，使带走的价值最大？这个看似简单的选择问题，实际上蕴含着动态规划最核心的思想——如何在约束条件下做出最优决策。 ...

给定一棵二叉树，找出其直径——这条路径可能穿过根节点，也可能完全在某个子树中。当你第一次看到 LeetCode 543 这道题时，可能会想：从根节点出发，找到最深的左节点和最深的右节点，把两条路径连起来不就是答案吗？但这个直觉会出错——直径可能根本不经过根节点。 ...

当你第一次尝试实现斐波那契数列时,可能会写出这样的递归代码: public int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } 这段代码看起来简洁优雅,但当 n 达到 50 时,程序会运行很长时间才能返回结果。问题出在哪里?重复计算。计算 fib(5) 时会调用 fib(3),计算 fib(4) 时又会再次调用 fib(3)。随着 n 增大,重复计算的次数呈指数级增长——时间复杂度高达 $O(2^n)$。 ...