第12章 动态规划算法

12.1 认识动态规划

动态规划（Dynamic Programming，简称 DP）是计算机科学中一种非常经典的算法思想。如果你是第一次接触这个名字，可能会觉得"动态规划"四个字听起来很抽象，不知道它到底在说什么。其实不必被名字吓到，它的核心思路可以用一句话来概括：把一个复杂的大问题拆解成若干个相对简单的小问题，先解决小问题，再利用小问题的答案逐步推导出大问题的解。

你可以把它想象成搭积木：要搭建一座高塔，你不会试图一次性把所有积木堆上去，而是从底层开始，一层一层稳稳地往上搭。每一层都建立在下一层的基础上，最终自然就搭成了完整的高塔。动态规划解决问题的方式与此非常相似——先算出最基础的子问题的答案，再用这些答案推出更大子问题的答案，层层递进，直到得出最终结果。

12.1.1 什么是动态规划

更准确地说，动态规划是一种通过将原问题分解为相互关联的子问题，并保存子问题的计算结果来避免重复计算，从而高效求解复杂问题的方法。它适用于具有两个关键特征的问题：一是重叠子问题，即在求解过程中，同一个子问题会被反复用到；二是最优子结构，即原问题的最优解可以由子问题的最优解推导而来。

举个简单的例子：计算斐波那契数列的第 N 项。如果用普通递归，计算 F(5) 需要计算 F(4) 和 F(3)，而计算 F(4) 又需要 F(3) 和 F(2)——你会发现 F(3) 被算了两次，F(2) 被算了更多次，大量计算是重复的。而动态规划的做法是：从 F(1)、F(2) 开始，把每一步的结果保存下来，后面需要用到时直接查表取值，不再重复计算。这样时间复杂度就从指数级的 O(2^N) 降低到了线性的 O(N)，效率提升是巨大的。

动态规划的求解过程通常包含4个核心步骤：

（1）定义子问题（或者叫状态）。

（2）找出子问题之间的递推关系（状态转移方程）。

（3）确定初始条件（边界值）。

（4）最后按照从小到大的顺序依次求解。

其中，状态转移方程是动态规划的灵魂，它描述了"当前问题的解如何从更小的子问题的解推导而来"，找到了这个方程，问题就基本解决了一大半。

12.1.2 历史与发展

动态规划的概念诞生于20世纪50年代，由美国数学家 Richard Bellman（理查德·贝尔曼）提出。当时贝尔曼在兰德公司从事运筹学研究，他在处理一类多阶段决策问题时发现，很多复杂问题都可以被分解为一系列相互关联的子问题，而且这些子问题之间存在重叠——也就是说，同一个子问题在不同的求解路径中会被反复遇到。基于这一观察，他提出了一种"逐步构建、保存中间结果"的求解思路，并将其命名为"动态规划"。

关于这个名字的由来，还有一个有趣的背景。据贝尔曼自己回忆，当时他需要一个听起来"不像数学"的名字来避免引起上级的反感（因为当时的政治环境对纯数学研究不太友好）。"动态"这个词听起来充满活力，而"规划"则暗示了实际的决策过程，两者结合既准确描述了方法的特征，又足够"无害"。这个名字就这样沿用至今。

贝尔曼最初将动态规划应用于控制论和运筹学领域，用来解决最优控制、资源分配等问题。后来随着计算机科学的发展，动态规划被引入到算法设计中，广泛应用于最短路径、背包问题、序列比对等经典问题。如今，动态规划的应用已经远远超出了计算机科学的范畴，在经济学、生物信息学、人工智能、机器学习等众多领域都发挥着重要作用。

12.1.3 重要性

在算法学习和实际应用中，动态规划的地位举足轻重。无论是算法竞赛（如 ACM、LeetCode）还是互联网大厂的技术面试，动态规划都是最高频的考察内容之一。这不是没有原因的——动态规划题目能够非常有效地考察一个人分析问题、抽象建模、推导递推关系的能力，它对逻辑思维的要求远高于普通的编码题。能否熟练运用动态规划，往往成为区分普通程序员和优秀算法工程师的重要标志。

从能力培养的角度来说，学习动态规划带来的收益远不止"会做 DP 题"这么简单。它训练的是一种"把大问题拆成小问题、从小问题的解构建大问题的解"的思维方式，这种思维方式在日常开发中同样受用——面对一个复杂的业务需求，能否清晰地拆解子任务、找到它们之间的依赖关系、确定正确的执行顺序，本质上和解动态规划问题是同一套思维模式。

总之，动态规划既是一种实用的算法工具，也是一种重要的思维训练。掌握了它，你不仅拥有了解决一大类复杂问题的能力，更提升了整体的算法设计和分析水平，为应对更高阶的技术挑战打下了坚实的基础。PS：在如今AI盛行的时代，解决复杂问题的底层能力变得更加重要，完成这趟思维训练之旅，理解AI的回复内容的速度更快，做事效率更高。

12.2 动态规划解题思路

12.2.1 核心思想

很多人第一次接触动态规划时，会觉得它高深莫测、晦涩难懂，甚至还没入门就产生了恐惧心理，最后直接放弃。其实完全没有必要。动态规划的核心思想用一句话就能说清楚：将一个复杂的大问题拆分为若干个相对简单的子问题，先求解子问题，再利用子问题的答案逐步构建出原问题的解。只要抓住了这个核心，再配合一套清晰的解题步骤，动态规划就不再神秘。

12.2.2 四个核心步骤

具体来说，动态规划的求解过程通常包含四个步骤。

第一步是定义状态，也就是把原问题拆分成若干个子问题，并用一个明确的表示方式（通常是数组或矩阵）来记录每个子问题的解。状态定义得好不好，直接决定了后续推导是否顺畅，因此这一步是整个动态规划的起点和基础。

第二步是确定状态转移方程，这是动态规划中最关键也是最有难度的一步。状态转移方程描述的是"当前状态的解如何从之前已知的状态推导而来"，它建立了子问题之间的递推关系。找到了正确的状态转移方程，问题就解决了一大半。

第三步是初始化状态，即确定最基础、最小的子问题的解作为起点，相当于递推的"第一块积木"，没有它，后续的推导就无从开始。

最后一步是计算原问题的解。根据状态转移方程，从初始状态出发，通过递归或迭代（循环）的方式逐步计算出所有子问题的解，最终得到原问题的答案。在这四个步骤中，状态定义和状态转移方程是动态规划的灵魂——状态定义决定了你"怎么看待这个问题"，状态转移方程决定了你"怎么解决这个问题"。掌握了这两点，动态规划的大门就算真正打开了。

我们可以从一个最简单的算法：斐波那契数列开始我们的动态规划。

12.3 斐波那契数列求解

1202年，意大利数学家列奥纳多·斐波那契（Leonardo Fibonacci）在其著作《计算之书》（Liber Abaci）中提出了一个有趣的兔子繁殖问题：假设一对刚出生的幼兔，一个月后成熟，再过一个月便能繁殖出新的一对幼兔，且每对兔子此后每月都会生出一对新兔，那么一年后一共有多少对兔子？这个看似简单的问题，催生出了一个影响深远的数列——斐波那契数列。更令人惊叹的是，这个数列后来被人们在自然界中反复发现：向日葵花盘上种子的螺旋排列、鹦鹉螺外壳的生长曲线、松果鳞片的旋向组合，无一不暗合斐波那契数列的规律，它因此也被称为"自然界的密码"。鹦鹉螺外壳的生长曲线如图12-1所示。

图12-1 鹦鹉螺外壳的生长曲线

斐波那契数列的定义非常简洁：第0个和第1个斐波那契数分别为0和1（即 F₀ = 0，F₁ = 1），从第2个数开始，每个数都等于前两个数之和，即 Fₙ = Fₙ₋₁ + Fₙ₋₂。由此可以得到 0、1、1、2、3、5、8、13、21、34…… 这样一组不断增长的数列。

定义虽然简单，但如果我们真正动手去编写一个函数，求解第 N 个斐波那契数的值，就会发现这个问题蕴含着丰富的算法设计思想，从中可以引出至少四种截然不同的求解策略：

（1）递归算法。

（2）记忆化搜索。

（3）动态规划的方案。

（4）动态规划 – 状态压缩。

12.3.1 递归算法

递归算法是一种基本且重要的算法思想，其核心在于"分而治之"：将一个大问题拆分成若干个结构相似但规模更小的子问题，再通过逐一解决这些子问题来解决整个大问题。在实现上，递归通常采用函数自身调用自身的方式，每一次调用都处理一个比上一层更小的问题，如此层层深入，直到问题的规模足够小、可以直接给出答案为止。这个"足够小、可以直接求解"的边界，就是递归函数的终止条件——它是递归能够正确结束而不陷入无限循环的关键保障。

用递归来求解斐波那契数列，是最直观也最贴近数学定义的做法。我们来看下面这段 TypeScript 代码：

▼
typescript
复制代码
function fibonacci(n: number): number {
  // 递归结束条件
  if (n <= 1) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
}

这段代码的逻辑非常清晰：当 n 小于等于 1 时，直接返回 n 本身（即 F₀ = 0，F₁ = 1），这就是递归的终止条件；否则，函数会递归地调用自身去分别计算第 n-1 个和第 n-2 个斐波那契数，再将两者相加作为结果返回。可以看到，代码几乎就是对数学定义 Fₙ = Fₙ₋₁ + Fₙ₋₂ 的逐字翻译，简洁而优雅。然而，这种优雅的背后隐藏着巨大的性能代价——在后续的分析中，我们会看到这种朴素递归为什么会慢到不可接受，以及如何一步步将它优化到极致。

以上是直观的做法递归：既然 Fₙ 由 Fₙ₋₁ 和 Fₙ₋₂ 定义，那就直接让函数调用自身去求解这两个子问题。代码写出来几乎和数学定义一模一样，优雅而易读，但它隐藏着严重的性能陷阱——大量的子问题被重复计算，时间复杂度呈指数级增长。

12.3.2 记忆化搜索

为了解决这个重复计算的问题，我们可以引入记忆化搜索：在递归的基础上，用一个数组或哈希表把已经计算过的结果缓存起来，下次遇到相同的子问题时直接查表返回，避免重复运算。这一步优化看似只加了几行代码，却将时间复杂度从指数级一举降到了 O(n)。记忆化搜索本质上是一种"自顶向下"的思路：我们从最终目标 Fₙ 出发，逐层向下拆解，遇到已知结果就停止递归。

▼
typescript
复制代码
function fib(n: number, memo: number[] = []): number {
  if (n <= 1) return n
  // 求n的值, 直接拿到值返回即可
  if (memo[n]) {
    return memo[n]
  }
  // 没有从memo中获取到值
  const res = fib(n - 1, memo) + fib(n - 2, memo)
  memo[n] = res // 将n位置的结果存储到memo中
  return res
}

console.log(fib(50))

从执行过程来看，记忆化搜索依然是"自顶向下"的递归结构——我们仍然从目标 Fₙ 出发，逐层拆解子问题。但有了备忘录之后，每一个子问题至多只会被真正计算一次。以求解 F₅ 为例：当递归沿左分支一路深入到 F₀ 和 F₁ 后开始回溯，F₂ 被第一次算出并存入 memo；随后计算 F₃ 时需要 F₂ 和 F₁，此时 F₂ 已经在备忘录中，直接查表返回，不再展开子树。整棵递归树从原来层层膨胀的二叉树，被"剪枝"成了一条近乎线性的链路。时间复杂度从朴素递归的 O(2ⁿ) 骤降至 O(n)，空间上则额外使用了一个长度为 n 的数组来存储中间结果。这就是为什么朴素递归求 F₅₀ 几乎不可能完成，而加上记忆化之后 却能瞬间给出结果——12586269025。

那么，朴素递归究竟会产生多少次重复计算？通过对比才能切实感受差距。

我们可以用具体的数字来感受一下。朴素递归求解 fib(n) 时，总的函数调用次数 T(n) 本身就满足一个递推关系：T(n) = T(n-1) + T(n-2) + 1——每次调用会产生两个子调用，再加上自身这一次。求解这个递推可以得到 T(n) = 2·Fₙ₊₁ - 1，也就是说，调用次数与斐波那契数同阶增长，约为 O(φⁿ)，其中 φ ≈ 1.618 是黄金比例。这意味着调用次数随 n 的增大呈指数级膨胀。

以求解 fib(50) 为例：朴素递归的总调用次数为 2 × F₅₁ - 1，约 407 亿次；而加上记忆化之后，总调用次数仅为 2n - 1 = 99 次。同样一个问题，一个需要 407 亿次函数调用，一个只需要 99 次，两者之间差了大约 4 亿倍。如果假设每次函数调用耗时 1 纳秒，朴素递归需要约 40 秒才能跑完，而记忆化搜索在微秒级就已经返回了结果。再把 n 拉大一点，差距会更加触目惊心：fib(100) 的朴素递归调用次数已经超过 10²⁰（万亿亿级别），即便动用当今最快的超级计算机，也无法在人类寿命内完成计算；而记忆化搜索依然只需要 199 次调用，瞬间给出答案。

12.3.3 动态规划方案

而如果我们换一个视角，选择"自底向上"地思考——从最小的子问题 F₀、F₁ 出发，逐步推导出 F₂、F₃……直到 Fₙ——这就是动态规划的经典范式。我们开辟一个长度为 n+1 的数组，按下标从小到大依次填表，每个位置只需要一次加法运算，整个过程没有递归调用的开销，逻辑也更加清晰可控。

在动态规划算法中，通常需要明确定义状态、设计状态转移方程、初始化状态，以及确定计算顺序等。

（1）状态定义：dp[i] 表示第 i 个斐波那契数的值。这是整个动态规划的基础——我们用一个数组的每个下标位置来代表一个子问题，dp[i] 存储的就是这个子问题的解。

（2）状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]。这是动态规划的核心，它描述了"当前子问题的解如何由更小的子问题的解推导而来"。在斐波那契数列中，这个关系恰好就是数列本身的定义。

（3）初始化状态：dp[0] = 0，dp[1] = 1。状态转移方程需要依赖前两个位置的值，因此最开始的两个位置必须手动赋初值，作为整个推导链条的起点。

（4）计算顺序：从 i = 2 开始，依次递增到 i = n。因为每个 dp[i] 依赖于 dp[i-1] 和 dp[i-2]，所以必须保证在计算当前位置时，它所依赖的两个位置已经被计算完毕——从小到大的顺序恰好满足这个要求。

将完整的斐波那契数列求出放入dp数组，再从dp数组的末尾拿出我们所需要的数据。PS：因为我们的斐波那契只计算到需求的位置，因此所需数据只会位于dp数组的尾端。

▼
typescript
复制代码
function fib(n: number): number {
  const dp: number[] = [0, 1]

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }

  return dp[n]
}

console.log(fib(50))

coderwhy老师的算法如下，区别在于斐波那契数列的头两位的处理角度上。我更倾向于将这有争议的两数字单独剥离出来，根据自己的实际需求去填写就好了。采用以下写法，需要注意区分n与i两个变量的应用位置。

▼
typescript
复制代码
function fib(n: number): number {
  // n位置的值: (n-1) + (n-2)
  const memo: number[] = []
  for (let i = 0; i <= n; i++) {
    // 初始化状态0和1位置对应的数字是0和1
    if (i <= 1) {
      memo[i] = i
      continue
    }
    // i = 0 memo[0] = 0
    // i = 1 memo[1] = 1
    // i = 2 memo[2] = 1
    // i = 3 memo[3] = 2
    memo[i] = memo[i - 1] + memo[i - 2]
  }
  return memo[n]
}

// console.log(fib(10)) // 55
console.log(fib(50))

export {}

动态规划的步骤拆分，理解如下：

▼
typescript
复制代码
function fib(n: number): number {
  // 1.定义状态
  // dp保留斐波那契数列中每一个位置对应的值(状态)
  // dp[x]表示的就是x位置对应的值(状态)
  // 2.状态转移方程: dp[i] = dp[i-1] + dp[i-2]
  // 状态转移方程一般情况都是写在循环(for/while)中
  // 3.设置初始化状态: dp[0]/dp[1]初始化状态
  // 4.计算最终的结果
  
  // 1.定义状态
  const dp: number[] = []
  // 2.初始化状态
  dp[0] = 0
  dp[1] = 1
  for (let i = 2; i <= n; i++) {
    // 3.状态转移方程
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  // 4.计算最终的结果
  return dp[n]
}

console.log(fib(10)) // 55
console.log(fib(50)) // 12586269025

export {}

12.3.4 状态压缩优化

在动态规划的基础上，我们还可以进一步观察到：计算 Fₙ 时，实际上只依赖 Fₙ₋₁ 和 Fₙ₋₂ 这两个值，并不需要保存整张表。于是我们可以用两个变量滚动更新。

在前面的动态规划版本中，我们开辟了一个长度为 n+1 的完整数组 dp，把从 F₀ 到 Fn 的每一个值都老老实实地存了下来。但如果我们回过头仔细观察状态转移方程 dp[i] = dp[i-1] + dp[i-2]，会发现一个关键事实：计算当前位置时，我们只向前看了两步，再往前的值从此再也不会被用到。换句话说，当我们算完 dp[5] 之后，dp[0]、dp[1]、dp[2]、dp[3] 就已经完成了它们的历史使命，继续占着内存纯属浪费。

基于这个观察，我们可以把整个数组替换成两个变量：prev 和 cur，分别扮演“前两个值”和“前一个值”的角色。

▼
typescript
复制代码
function fib(n: number): number {
  if (n <= 1) return n

  // 1.定义状态和2.初始化状态
  let prev = 0
  let cur = 1

  for (let i = 2; i <= n; i++) {
    // 3.状态转移方程
    const newValue = prev + cur
    prev = cur
    cur = newValue
  }
  // 4.计算最终的结果
  return cur
}

console.log(fib(10)) // 55
console.log(fib(50)) // 12586269025

export {}

整个过程就像一扇只能看到两格的滑动窗口在数列上向右移动。这其实很类似一个游戏，我有三块木板（newValue，prev和cur），其中prev和cur是我双脚前后正踩着的，我要往前进，我将手里的newValue捡起来往前放，然后后脚从cur站到prev上，前脚从prev站到newValue上，然后将位于最后的cur木板回收一下，继续往前铺。全程只需要用到三块木板，而不用很多块木板铺出一整条后续用不上的路，这些木板会占据着我们的内存，只用三块木板完成目标，意味着我们用极少的内存完成需求。PS：我很建议大家在大脑内，可视化的去想象这个游戏画面，就很容易理解并写出对应代码。

空间复杂度从 O(n) 降到了 O(1)。这种优化手法在动态规划中被称为状态压缩——当状态转移方程只依赖有限个前驱状态时，我们就不必保存完整的历史记录，只需用有限的几个变量"滚动"前进即可。它的本质是对空间维度的极致节约：只留下还有用的，丢掉已经用完的。

从递归到记忆化搜索，再到动态规划，最后到状态压缩，这四种方法层层递进，完整地展示了一个算法从"能跑"到"跑得快"再到"跑得省"的优化历程——而这，正是动态规划最核心的思维方式。

12.3.5 LeetCode实战：斐波那契数(509)

LeetCode上的斐波那契数题目位于509题，地址：509. 斐波那契数 - 力扣（LeetCode）。

题目如下：

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

▼
plain
复制代码
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

用12.3.4小节的状态压缩优化来做这道题目，如下：

▼
typescript
复制代码
function fib(n: number): number {
    if (n <= 1) return n
    let prev = 0
    let cur = 1
    for(let i = 2; i <= n ; i++) {
        const newValue = prev + cur
        prev = cur
        cur = newValue
    }
    return cur
};

LeetCode斐波那契数执行效果如图12-2所示，耗时击败100%。

图12-2 LeetCode斐波那契数执行效果

12.4 跳台阶问题求解

掌握了斐波那契数列的四种求解思路之后，我们来看一道经典的动态规划题目——爬楼梯，也有人称之为跳台阶（我个人一直习惯叫跳台阶）。

题目描述很简单：假设有 n 级台阶，每次可以跳 1 级或 2 级，问一共有多少种不同的跳法可以跳到第 n 级台阶。

这道题在面试中出现的频率极高，而它之所以经典，是因为它的本质和斐波那契数列如出一辙——要到达第 n 级台阶，你只可能从第 n-1 级跳 1 步上来，或者从第 n-2 级跳 2 步上来，除此之外别无他路。因此，到达第 n 级台阶的跳法总数，就等于到达第 n-1 级的跳法数加上到达第 n-2 级的跳法数，即 dp[n] = dp[n-1] + dp[n-2]。

这个状态转移方程和斐波那契数列的递推公式在结构上完全一致，区别仅在于初始值：斐波那契数列的起点是 F₀ = 0、F₁ = 1，而跳台阶问题中，站在地面（第 0 级）算 1 种方案，跳到第 1 级也只有 1 种方案，因此 dp[0] = 1、dp[1] = 1。有了前面从递归到记忆化搜索，再到动态规划和状态压缩的完整铺垫，解决这道题不过是换一组初始值、套用同样的思维框架而已，一旦掌握了核心范式，面对新问题时只需识别出"状态"和"转移方程"，解法便水到渠成。

这道题目我们依然采用4种不同的方案来实现，让大家体会到动态规划的好处：

（1）暴力递归。

（2）记忆化搜索。

（3）动态规划。

（4）状态压缩。

12.4.1 暴力递归

暴力递归的思路最为直观：既然到达第 n 级台阶只可能从第 n-1 级或第 n-2 级跳上来，那我们就让函数递归地去求解这两个子问题，把结果相加即可。递归的终止条件也很自然——当 n 等于 0 或 1 时，只有 1 种跳法（站在原地不动，或者只跳 1 级），直接返回 1。

▼
typescript
复制代码
function climbStairs(n: number): number {
  if (n <= 1) return 1
  return climbStairs(n - 1) + climbStairs(n - 2)
}

console.log(climbStairs(10)) // 89

这段代码几乎是对状态转移方程 dp[n] = dp[n-1] + dp[n-2] 的逐字翻译，写法上和之前斐波那契的递归版本如出一辙，唯一的区别在于终止条件：斐波那契中 n ≤ 1 时返回 n（即 F₀ = 0，F₁ = 1），而跳台阶中 n ≤ 1 时返回 1（即 dp[0] = 1，dp[1] = 1）。同样地，这种朴素递归也继承了斐波那契递归版本的致命缺陷——大量的重复计算。以 climbStairs(5) 为例，climbStairs(3) 会被计算 2 次，climbStairs(2) 会被计算 3 次，随着 n 的增大，重复计算呈指数级膨胀，时间复杂度高达 O(2ⁿ)，在 n 稍大时便完全不可用。这也正是我们需要继续优化的原因。

12.4.2 记忆化搜索

既然暴力递归的瓶颈在于重复计算，解决办法我们已经在斐波那契数列中见过了——给递归加上一块"备忘录"。思路完全一致：在递归过程中，每当一个子问题第一次被计算出来，就把结果存入备忘录；之后再遇到同样的子问题时，直接查表返回，不再重复展开递归树。

▼
typescript
复制代码
function climbStairs(n: number, memo: number[] = []): number {
  if (n <= 1) return 1
  if (memo[n]) {
    return memo[n]
  }
  const res = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
  memo[n] = res
  return res
}

console.log(climbStairs(50)) // 20365011074

可以看到，代码结构与斐波那契的记忆化版本几乎一模一样，改动的地方只有终止条件——n ≤ 1 时返回 1 而非 n。函数每次进入后先检查备忘录中是否已有当前子问题的答案，如果有就直接返回，避免了一切重复计算；如果没有，才真正执行递归，并在返回前将结果写入 memo[n] 供后续查询。经过这一层优化，原本指数级膨胀的递归树被大幅剪枝，每个子问题至多只被计算一次，时间复杂度从 O(2ⁿ) 降至 O(n)，这就是为什么 climbStairs(50) 能够瞬间给出结果。到这里，记忆化搜索的套路已经非常清晰了：无论是斐波那契还是跳台阶，只要递归中存在重复子问题，加上一个备忘录就能带来质的飞跃——这个模式在后续更复杂的动态规划题目中同样适用。

12.4.3 动态规划

从记忆化搜索到动态规划，思维方式的转换我们在斐波那契数列中已经体验过一次：把"自顶向下"的递归改为"自底向上"的填表。具体到跳台阶问题，我们定义一个长度为 n+1 的一维数组 dp，其中 dp[i] 表示到达第 i 级台阶的跳法数量。初始时将数组中所有元素都置为 0，然后设置 dp[0] = 1、dp[1] = 1，表示站在地面和跳到第 1 级台阶各只有 1 种方案。有了这两个起点，我们就可以从 i = 2 开始循环，依次计算 dp[2]、dp[3]……直到 dp[n]，每一步都只是把前两个位置的值相加填入当前位置，最终 dp[n] 就是我们要的答案。

▼
typescript
复制代码
function climbStairs(n: number): number {
  // 1.定义状态
  // dp = [每一阶台阶不同的方法]
  // dp[3] = xx
  // 2.确定状态转移方程
  // dp[i] = dp[i-1] + dp[i-2]
  // 3.初始化状态
  // dp[0] = 1
  // dp[1] = 1
  // 思考: dp[2] = 2
  // 思考: dp[3] = 3
  // 思考: dp[4] = 2 + 3 = 5
  // 4.最终的答案: dp[n]
  const dp: number[] = new Array(n + 1).fill(0)
  dp[0] = 1
  dp[1] = 1

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }

  return dp[n]
}

console.log(climbStairs(50)) // 20365011074

整个过程没有递归调用、没有函数栈的层层嵌套，就是一次简单的从左到右的线性遍历。与记忆化搜索相比，两者的时间复杂度同为 O(n)，但动态规划省去了递归调用的额外开销，执行效率更高，逻辑也更加清晰可控——数组里的每一个位置从前到后依次被填满，每个值的来源一目了然。而如果你对比斐波那契的动态规划版本，会发现两段代码在结构上几乎完全相同，差异仅仅在于初始值从 dp[0] = 0、dp[1] = 1 变成了 dp[0] = 1、dp[1] = 1。同一套范式，换一组初始条件，就解决了一道新的问题——这就是动态规划"一法通，万法通"的复用能力。

12.4.4 滚动数组（滑动窗口）优化

回顾状态转移方程 dp[i] = dp[i-1] + dp[i-2]，每一步计算只依赖前两个状态的值，再往前的历史数据从此不会被用到。既然如此，我们就没有必要维护一整个长度为 n+1 的数组，只需要两个变量滚动前进即可。这种优化手法也被称为滚动数组，它的基本思想是：当每个状态只与它之前的有限个状态有关时，我们不需要记录所有的状态，只需要记录当前状态和它之前的若干个状态，通过不断更新这个滚动窗口来完成整个推导过程。

▼
typescript
复制代码
function climbStairs(n: number): number {
  if (n <= 1) return 1
  // 1.定义状态
  let prev = 1 // 对应 dp[0]
  let cur = 1 // 对应 dp[1]
  // 3.状态转移方程
  for (let i = 2; i <= n; i++) {
    const newValue = prev + cur
    prev = cur
    cur = newValue
  }

  return cur
}

console.log(climbStairs(50)) // 20365011074

和之前那个"三块木板游戏"的比喻差不多。这里的过程完全一样：prev 和 cur 是脚下踩着的两块板，newValue 是手中的备用板，每一轮循环把备用板往前铺一格，然后整个人向前迈一步，身后空出的旧板捡起来留作下一轮使用。从 (1, 1) 出发，窗口一路滚动到第 n 个位置，最终 cur 中存放的就是答案。时间复杂度依然是 O(n)，而空间复杂度从数组版本的 O(n) 降到了 O(1)，全程只用三个变量就完成了全部计算。

PS：在不知道动态规划的情况下，在我看到该题目的第一眼，思路如下：踏上第1级台阶，后续有x种可能，踏上第2级台阶；后续有y种可能。无论是x或者y，都是基于后续跳动的1级与2级的组合情况，假设n阶是一个比较庞大的数字，无需计算就可以预估踏上台阶的第一步，后续可能性是一个庞大的数字。因此可以从第n级台阶往回推，第n-1级台阶只有往上踏出1级的可能性，第n-2级台阶既可以往上踏出两次1级也可以一次性踏出2级，我可以先简单算出第n-1，n-2，n-3个台阶有几种可能，并基于可能存在的规律算出每个台阶的可能性公式，逆推问题。

12.4.5 LeetCode实战：爬楼梯(70)

爬楼梯位于LeetCode的第70道题目，地址：70. 爬楼梯 - 力扣（LeetCode）。

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

这里不再重复解答效果，可以将12.4.4小节的优化代码写入其中自行测试。

12.5 股票买卖最大值问题

题目：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。只能选择某一天买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

这道题的应用场景其实非常广泛，远不止股票交易这一个领域。

最直接的场景当然是金融投资。在真实的股票市场中，每一个交易者都在面对同样的问题：回顾一段时间内的价格走势，找出最佳的买入和卖出时机以获取最大利润。当然，现实中的股票交易远比这道题复杂——需要考虑手续费、印花税、滑点、涨跌停限制、T+1 交割制度等等。但这道题抽象出了最本质的那个问题：在一条时间序列上，找到一个低点买入、一个高点卖出，使差值最大。这个抽象模型是量化交易策略中很多回测算法的基础起点，华尔街的量化团队在构建更复杂的交易模型之前，往往就是从这类最简单的"单次交易最优解"问题开始迭代的。

但如果跳出金融领域，会发现这个问题的结构无处不在。比如能源行业中，电力公司需要决定何时从市场上低价购入电力储存、何时高价卖出——电价随时段和季节剧烈波动，本质上就是同一道题。大宗商品贸易也是如此，粮食、石油、金属的贸易商每天面对的核心决策就是"什么时候进货、什么时候出货"。甚至在日常生活中，如果你关注某个商品的历史价格走势，想找出过去一年中最佳的购买时机，本质上也是在求解这道题。

12.5.1 动态规划实现思路

股票买卖最大利润的问题要如何解决？直觉告诉我们，最大利润就是在最低点买入、最高点卖出。但问题在于——什么时候是最低点，什么时候又是最高点？如果我们拥有"上帝视角"，能一眼看穿整条价格曲线的全貌，那直接找到全局最小值和它之后的全局最大值就好了。然而这道题的精妙之处恰恰在于：我们必须模拟真实的决策场景，把视野局限在"当下"——站在第 i 天的时候，你只知道今天及之前的所有价格，未来的走势一无所知。你不可能知道明天是不是最高点，也不可能确认今天就是最低点。

既然无法预知未来，我们就换一个思路：不去追问"全局最低点在哪里"，而是在每一天都问自己一个更简单的问题——"截至今天为止，历史最低价是多少？" 这个问题随着时间的推移可以被轻松维护：每到一个新的交易日，只需要拿当天的价格和之前记录的最低价做一次比较，取较小值更新即可。有了这个"截至当前的历史最低价"，我们在每一天都可以计算出"如果今天卖出，能获得的最大利润"——就是当天价格减去历史最低价。然后，我们只需要在整个遍历过程中，持续追踪这个利润的最大值，走完整条价格曲线之后，手里记录的就是全局最大利润。

这个思路的巧妙之处在于，它把一个看似需要两层嵌套（枚举所有买卖组合）的 O(n²) 问题，转化成了一次线性遍历就能解决的 O(n) 问题。每一天只做两件事：更新历史最低价，计算当前利润并尝试刷新最大值。

▼
typescript
复制代码
function maxProfit(prices: number[]): number {
  // 1.定义状态: dp[i]
  // * 到i天能获取到的最大收益是多少
  // 2.状态转移方程
  // dp[i] = max(dp[i - 1], price[i] - minPrice)
  // 3.初始化状态: dp[0] = 0
  // 4.获取最后一次的值 dp[n-1]
  const n = prices.length
  if (n <= 1) return 0

  // 1.定义状态
  const dp: number[] = []
  // 2.设置初始化值
  dp[0] = 0
  // 3.状态转移方程求dp[i]
  let minPrice = prices[0]
  for (let i = 1; i < n; i++) {
    // 当前i位置 - 前一个最小值
    dp[i] = Math.max(prices[i] - minPrice, dp[i - 1])
    minPrice = Math.min(prices[i], minPrice)
  }

  return dp[n-1]
}

console.log(maxProfit([7,1,5,3,6,0,4]))

export {}

所以这道题的原理是在计算过往情况，将过去的最低点保存下来，当未来变到正在发生时，计算当下与最低点的差值，当计划范围内的未来都变成过去时，我们就可以知道曾经的最大收益是多少。

这道题实际告诉我们永远不可能精准地"抄底逃顶"，因为站在任何一个时刻的我们都不知道未来会怎样。这道题的题目看似在告诉我们如何买卖股票可以获得最大收益，但实际的应用场景只能告诉我们曾经的最大涨幅，大涨幅意味着大波动，大波动意味着不稳定。如果把这道题的比较逻辑反转一下，维护"截至当前的历史最高价"，然后每天计算"从最高点跌到今天跌了多少"，那就是真正意义上的最大回撤算法了。回撤幅度越大，修复时间越久的股票，具备的风险就越大。

所以我认为这道题很有意思，这个算法真正的实战价值，是回顾性的，帮助我们在一切尘埃落定之后，量化一段行情中曾经出现过的极端波动。这道题看似在教人赚钱，背后实际在说的事情是注意风险，敬畏风险。

12.5.2 状态压缩优化

和前面的斐波那契、跳台阶一样，这道题同样可以进行状态压缩。回顾动态规划版本的状态转移方程 dp[i] = Math.max(prices[i] - minPrice, dp[i-1])，可以发现 dp[i] 只依赖于 dp[i-1] 这一个前驱状态，再往前的 dp[i-2]、dp[i-3]…… 全部不会被用到。既然如此，我们就不需要一整个数组来记录所有历史状态，只需要一个变量 preValue 滚动更新即可。

▼
typescript
复制代码
function maxProfit(prices: number[]): number {
  const n = prices.length
  if (n <= 1) return 0

  // 1.定义状态
  // const dp: number[] = []
  // 2.设置初始化值
  let preValue = 0
  // 3.状态转移方程求dp[i]
  let minPrice = prices[0]
  for (let i = 1; i < n; i++) {
    // 当前i位置 - 前一个最小值
    // 这里可以压缩的原因: i位置的值, 只和前一个位置有关系
    preValue = Math.max(prices[i] - minPrice, preValue)
    minPrice = Math.min(prices[i], minPrice)
  }

  return preValue
}

console.log(maxProfit([7,1,5,3,6,0,4]))

export {}

对比动态规划版本，改动非常小：原来的 dp 数组被一个变量 preValue 替代，它始终存储着"截至上一轮循环为止的最大利润"。每进入新一轮循环，preValue 在"当天卖出的利润"和"之前已经取得的最大利润"之间取较大值，然后自身被更新为新的最大利润，原来的旧值自然被覆盖——这就完成了一次"滚动"。整个过程中，preValue 扮演的角色和跳台阶中的 cur 完全一致：它不记录完整的历史，只保留当下最需要的那一个值，用最少的内存完成同样的计算。时间复杂度依然是 O(n)，空间复杂度则从 O(n) 降到了 O(1)。至此，买卖股票问题的动态规划解法也完成了从"完整填表"到"极致压缩"的最后一步优化。

12.5.3 LeetCode实战：买卖股票最佳时机(121)

买卖股票的最佳时机位于LeetCode的第121道题目，地址：121. 买卖股票的最佳时机 - 力扣（LeetCode）。

12.6 最大子数组和问题

更有意思的是，股票买卖最大值问题在计算机科学中还有一个经典的别名——最大子数组差值问题（Maximum Subarray Difference）。如果我们把相邻两天的价格差构成一个新数组，那么"买卖股票的最大利润"就等价于在这个差值数组上求最大子数组和，而这正是另一道经典的动态规划题目——第 53 题「最大子数组和」（Kadane's Algorithm）。两道看似不同的题目，底层的数学结构竟然完全等价，这也是算法之美的一个缩影。

题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

12.6.1 动态规划实现思路

最大子数组和的动态规划思路，也是找出4个关键因素：

（1）定义状态。

（2）初始化值。

（3）状态转移方程。

（4）求出问题的解。

这道题的关键在于理解"连续"这个约束。子数组必须是数组中一段连续的元素，不能跳着选。那么站在数组的第 i 个位置，我们面临的核心决策其实只有一个：要不要把自己接到前面那段子数组的尾巴上？

我们来逐一拆解动态规划的四个要素。

状态定义：dp[i] 表示以 nums[i] 为结尾的连续子数组的最大和。注意这里的关键词是"以 nums[i] 结尾"——这意味着 nums[i] 这个元素必须被选中，它是子数组的最后一个元素。这个定义方式非常重要，因为它天然地保证了子数组的连续性：dp[i] 描述的那段子数组一定紧贴着第 i 个位置，往前延伸若干格。

初始化值：dp[0] = nums[0]。第一个元素自成一个子数组，没有前驱可以接，最大和就是它自身。

状态转移方程：这是这道题最需要想清楚的部分。站在第 i 个位置，我们有且仅有两个选择——要么把 nums[i] 接到以 nums[i-1] 结尾的那段最优子数组后面，形成一段更长的连续子数组，此时和为 dp[i-1] + nums[i]；要么抛弃前面的一切，从 nums[i] 自己重新开始一段新的子数组，此时和就是 nums[i] 本身。什么时候应该抛弃前面的累积？答案很直觉——当前面那段子数组的最大和已经是负数的时候。一个负数加上当前值只会拖后腿，还不如从头再来。因此状态转移方程为：dp[i] = Math.max(dp[i-1] + nums[i], nums[i])。

• 如果前面的子序列是负数，那么最大子序列和一定是自己。
• 如果前面的子序列是正数，那么最大子序列和是自己+前值。

求出问题的解：这里有一个容易踩的坑。最终答案不是 dp[n-1]，而是整个 dp 数组中的最大值。因为 dp[i] 的定义是"以第 i 个元素结尾的最大子数组和"，最优子数组不一定以最后一个元素结尾，它可能出现在数组的任何位置。所以我们需要在遍历填表的过程中，额外维护一个变量来追踪 dp 数组的全局最大值，遍历结束后这个最大值就是答案。

▼
typescript
复制代码
function maxArray(nums: number[]): number {
  // 1.定义状态 dp[i]
  // * 以i位置的元素结尾的连续数组能获取到的最大值
  // dp[0] = 3
  // dp[1] = 8
  // dp[2] = 9
  // dp[3] = -1
  // dp[4] = max(nums[i], dp[3] + nums[i])
  // dp[4] = max(8, -1 + 8  = 7) = nums[i] = 8
  // dp[5] = -4
  // dp[6] = 10

  // 2.状态转移方程
  // dp[i] = max(num[i], dp[i-1] + nums[i])

  // 3.初始化状态 dp[0] = 3

  // 4.最终值 遍历整个dp获取到最大的值

  // 1.获取数组的长度
  const n = nums.length

  // 2.定义状态
  const dp: number[] = []

  // 3.初始化状态
  dp[0] = nums[0]

  // 4.状态转移的过程
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])
  }

  return Math.max(...dp)
}

console.log(maxArray([-2,1,-3,4,-1,2,1,-5,4]))

export {}

只需要理解了"连续"的概念就很容易将最大子数组和做出来，因为一段数组中，我们可以可以获取到数组的长度和内容的。我们完全可以"骑驴找马"，手里的更好就拿着，外面的更好就换，仅此而已。这题也是类似的想法，前面累积的子数组和就像是过去的投入，如果它是正数，说明这笔"家底"对当下还有贡献，值得带着继续走；但一旦它变成了负数，就意味着过去的累积已经变成了拖累——再好的当下加上一个负数也只会变差。这时候最理智的做法就是果断"止损"，把过去的沉没成本全部舍弃，从当前元素重新开始积累。

在完整的数组阶段中，总会起起伏伏，最高光的时刻未必是在最后，所以我们要怎么选中最高光的时刻？例如[0,2,3,4,5,-15,3]，我在前五位和是14，加上第六位之后的和是-1,-1加3是拖累，所以舍弃掉之前的积累，但整体最大的和（最高光时刻）依旧是14，而不是舍弃沉没成本之后的3。

答案藏在代码的最后一行：return Math.max(...dp)。假设所有的阶段都是高光时刻，抛弃所有会令我们下落的可能性（即过去积累+现在<现在），我们将每个阶段的情况都记录下来，在所有高光时刻中，选择最高光的那一种情况。

12.6.2 状态压缩优化

同样地，观察状态转移方程 dp[i] = Math.max(nums[i], dp[i-1] + nums[i])，可以发现 dp[i] 只依赖于 dp[i-1] 这一个前驱状态，再往前的值一概不会被用到。因此我们可以用一个变量 preValue 来替代整个 dp 数组，滚动记录"以上一个位置结尾的最大子数组和"。但这道题和前面的斐波那契、跳台阶有一个不同之处：最终答案不是 dp 数组的最后一个值，而是整个数组中的最大值。一旦压缩掉了 dp 数组，我们就失去了"事后回头翻阅整张表"的能力，所以必须在遍历过程中同步维护一个 max 变量，实时追踪全局最大值。

▼
typescript
复制代码
function maxArray(nums: number[]): number {
  // 1.获取数组的长度
  const n = nums.length
  let preValue = nums[0]

  // 4.状态转移的过程
  let max = preValue
  for (let i = 1; i < n; i++) {
    preValue = Math.max(nums[i], nums[i] + preValue)
    max = Math.max(preValue, max)
  }

  return max
}

console.log(maxArray([-2,1,-3,4,-1,2,1,-5,4]))

export {}

代码中 preValue 扮演的角色就是被压缩掉的 dp[i-1]：每一轮循环先通过状态转移方程算出当前位置的最优值，覆盖到 preValue 上，旧值自然被丢弃；紧接着用 max = Math.max(preValue, max) 把这个新算出来的值和全局最大值做一次比较，如果刷新了纪录就更新 max。这两行代码分别对应着前面说的两件事——preValue 负责"在每个当下做出最优选择"，max 负责"在所有最优选择中选出全局冠军"。只不过在完整 dp 数组的版本中，这两件事是分开的：先填完整张表，再遍历一次找最大值；而在状态压缩版本中，这两件事被合并到了同一轮循环里同步完成。最终效果是一样的，时间复杂度依然是 O(n)，但空间复杂度从 O(n) 降到了 O(1)。

不需要记录所有高光时刻，只需要在每个高光时刻出现的瞬间就地比较，走完全程，最高光的那个自然留在手中。

12.6.3 LeetCode实战：最大子数组和(53)

最大子数组和位于LeetCode的第53道题目，地址：53. 最大子数组和 - 力扣（LeetCode）。