dynamic-programming

用途：当问题同时具备重叠子问题（同一计算被反复执行）与最优子结构（最优解由最优子解构成）时使用动态规划。常见信号包括“求最小成本”“计算方案数”“最长/最短子序列”“能否到达”。主要能力与规则：先定义状态（子问题之间变化的量）与递推关系（状态如何关联）；自顶向下配合 @cache 最易书写，自底向上的制表法可避免递归深度限制且通常更快；始终检查能否只保留上一行/上一状态来压缩空间，而非保存整张表；切勿在未确认存在重叠子问题时就使用记忆化。使用方式：一、识别状态变量；二、写出递推关系；三、选择自顶向下（@cache）或自底向上（制表法）；四、尽可能做空间优化。例如“凑出金额所需最少硬币”中，状态为剩余金额，递推为 dp(n) = 1 + min(dp(n - c) for c in coins)，自顶向下用 @cache，空间可降至 O(amount)。限制：资料未提供更多实现细节、适用语言版本或平台支持信息。