动态规划算法详解

发表于 2026-03-18 分类于算法阅读次数：

本文字数： 9.9k 阅读时长 ≈ 9 分钟

动态规划（Dynamic Programming，DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它的核心思想是利用历史记录避免重复计算。本文将从基础到进阶，全面讲解动态规划。

一、什么是动态规划？

1.1 核心思想

动态规划的本质就是利用历史记录避免重复计算。这些历史记录通常用一维数组或二维数组来保存。

通俗理解：

你要爬 10 级楼梯，每次可以爬 1 级或 2 级。
爬到第 10 级的方法 = 爬到第 9 级的方法 + 爬到第 8 级的方法
因为最后一步要么从第 9 级爬 1 级，要么从第 8 级爬 2 级
这样我们只需要记录爬到第 1-9 级的方法数，就能算出第 10 级的方法数

1.2 动态规划三步骤

做动态规划题时，只要按这三个步骤走，大部分题目都能迎刃而解：

步骤	说明	关键问题
第一步	定义 dp 数组元素的含义	dp[i] 代表什么？
第二步	找出数组元素之间的关系式（状态转移方程）	dp[n] 如何通过 dp[n-1], dp[n-2]… 推导出来？
第三步	找出初始值	dp[0], dp[1]… 的值是多少？

二、动态规划三步骤详解

2.1 第一步：定义 dp 数组元素的含义

这一步最关键，你想求什么，就定义 dp[i] 是什么！

示例：

爬楼梯问题：dp[i] 表示爬到第 i 级楼梯的方法数
斐波那契数列：dp[i] 表示第 i 个斐波那契数
最大子数组和：dp[i] 表示以第 i 个元素结尾的最大子数组和
最长递增子序列：dp[i] 表示以第 i 个元素结尾的最长递增子序列长度

2.2 第二步：找出状态转移方程

这是最难的一步，但也是最有技巧的一步。类似于数学归纳法，当我们要计算 dp[n] 时，可以利用 dp[n-1], dp[n-2], …, dp[1] 来推导。

常见的状态转移方程模式：

模式	示例	适用题型
`dp[n] = dp[n-1] + dp[n-2]`	爬楼梯、斐波那契	一维线性问题
`dp[n] = max(dp[n-1], dp[n-2] + nums[n])`	打家劫舍	选择/不选择问题
`dp[i][j] = dp[i-1][j] + dp[i][j-1]`	不同路径	二维网格问题
`dp[i][j] = dp[i-1][j-1] + 1` (if s[i]==t[j])	最长公共子序列	双序列问题

2.3 第三步：找出初始值

有了状态转移方程，我们还需要初始值才能递推。初始值就是那些不能再分解的基础情况。

示例：

爬楼梯：dp[0] = 1, dp[1] = 1（0 级楼梯 1 种方法，1 级楼梯 1 种方法）
斐波那契：dp[0] = 0, dp[1] = 1
不同路径：dp[0][j] = 1, dp[i][0] = 1（第一行和第一列都只有 1 种走法）

三、经典例题详解

3.1 例题一：爬楼梯

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

解法：

第一步：定义 dp 数组的含义

dp[i]：爬到第 i 级楼梯的方法数

第二步：找出状态转移方程

要爬到第 i 级，最后一步要么从第 i-1 级爬 1 级，要么从第 i-2 级爬 2 级
所以：dp[i] = dp[i-1] + dp[i-2]

第三步：找出初始值

dp[0] = 1（0 级楼梯，不爬也是一种方法）
dp[1] = 1（1 级楼梯，只有 1 种方法）

代码实现：

function climbStairs(n) {
  if (n <= 1) return 1;
  
  const dp = new Array(n + 1);
  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(5)); // 8

空间优化：
我们发现计算 dp[i] 只需要 dp[i-1] 和 dp[i-2]，不需要保存整个数组：

function climbStairs(n) {
  if (n <= 1) return 1;
  
  let prev = 1;   // dp[i-2]
  let curr = 1;   // dp[i-1]
  
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  
  return curr;
}

3.2 例题二：打家劫舍

题目：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

解法：

第一步：定义 dp 数组的含义

dp[i]：前 i 间房屋能偷窃到的最高金额

第二步：找出状态转移方程

对于第 i 间房屋，有两种选择：
- 偷：那么第 i-1 间不能偷，最高金额 = dp[i-2] + nums[i]
- 不偷：最高金额 = dp[i-1]
所以：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

第三步：找出初始值

dp[0] = nums[0]（只有 1 间房，只能偷它）
dp[1] = max(nums[0], nums[1])（两间房，偷金额大的那间）

代码实现：

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  
  const dp = new Array(nums.length);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  
  return dp[nums.length - 1];
}

console.log(rob([1,2,3,1])); // 4
console.log(rob([2,7,9,3,1])); // 12

空间优化：

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  
  let prevPrev = nums[0];   // dp[i-2]
  let prev = Math.max(nums[0], nums[1]);  // dp[i-1]
  
  for (let i = 2; i < nums.length; i++) {
    const curr = Math.max(prev, prevPrev + nums[i]);
    prevPrev = prev;
    prev = curr;
  }
  
  return prev;
}

3.3 例题三：不同路径

题目：
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start”）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。问总共有多少条不同的路径？

示例：

1 2	输入：m = 3, n = 7 输出：28

解法：

第一步：定义 dp 数组的含义

dp[i][j]：从起点 (0,0) 走到 (i,j) 的路径数

第二步：找出状态转移方程

要走到 (i,j)，只能从上面 (i-1,j) 走下来，或者从左边 (i,j-1) 走过来
所以：dp[i][j] = dp[i-1][j] + dp[i][j-1]

第三步：找出初始值

第一行：dp[0][j] = 1（只能一直向右走）
第一列：dp[i][0] = 1（只能一直向下走）

代码实现：

function uniquePaths(m, n) {
  const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
  
  // 初始化第一行
  for (let j = 0; j < n; j++) {
    dp[0][j] = 1;
  }
  
  // 初始化第一列
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1;
  }
  
  // 填充 dp 数组
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  
  return dp[m - 1][n - 1];
}

console.log(uniquePaths(3, 7)); // 28
console.log(uniquePaths(3, 2)); // 3

空间优化：
我们可以用一维数组代替二维数组：

function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);
  
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] = dp[j] + dp[j - 1];
    }
  }
  
  return dp[n - 1];
}

3.4 例题四：最长递增子序列（LIS）

题目：
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

示例：

1
2
3

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。

解法：

第一步：定义 dp 数组的含义

dp[i]：以第 i 个元素结尾的最长递增子序列的长度

第二步：找出状态转移方程

对于第 i 个元素，我们需要看它前面所有比它小的元素
如果 nums[j] < nums[i]，那么 dp[i] = max(dp[i], dp[j] + 1)
所以：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]

第三步：找出初始值

每个元素自身就是一个长度为 1 的子序列
所以：dp[i] = 1 对所有 i

代码实现：

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  
  const dp = new Array(nums.length).fill(1);
  let maxLen = 1;
  
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }
  
  return maxLen;
}

console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4
console.log(lengthOfLIS([0,1,0,3,2,3])); // 4

3.5 例题五：0-1 背包问题

题目：
有一个背包，它的容量为 C。现在有 n 个物品，第 i 个物品的重量为 w[i]，价值为 v[i]。问如何选择物品装入背包，使得总价值最大？

示例：

输入：C = 4, w = [1, 2, 3], v = [6, 10, 12]
输出：22
解释：选物品 1 和物品 2，总重量 3，总价值 16？不对，应该是选物品 1 和物品 3，总重量 4，总价值 18？
      哦，最佳是选物品 2 和物品 3？重量 5 超过了...
      正确答案：选物品 1 和物品 2，总重量 3，总价值 16，或者选物品 3，重量 3，价值 12？
      等一下，让我重新算：
      容量 4：
      - 物品 1 + 物品 2：重量 1+2=3 ≤4，价值 6+10=16
      - 物品 1 + 物品 3：重量 1+3=4 ≤4，价值 6+12=18
      - 物品 2 + 物品 3：重量 2+3=5 >4，不行
      - 只物品 3：重量 3，价值 12
      所以最佳是 18！

解法：

第一步：定义 dp 数组的含义

dp[i][j]：前 i 个物品，容量为 j 时的最大价值

第二步：找出状态转移方程

对于第 i 个物品，有两种选择：
- 不选：dp[i][j] = dp[i-1][j]
- 选（如果 j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
所以：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

第三步：找出初始值

dp[0][j] = 0（没有物品，价值为 0）
dp[i][0] = 0（容量为 0，价值为 0）

代码实现：

function knapsack(C, w, v) {
  const n = w.length;
  const dp = new Array(n + 1).fill(0).map(() => new Array(C + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= C; j++) {
      // 不选第 i 个物品
      dp[i][j] = dp[i - 1][j];
      
      // 选第 i 个物品（如果容量足够）
      if (j >= w[i - 1]) {
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
      }
    }
  }
  
  return dp[n][C];
}

console.log(knapsack(4, [1, 2, 3], [6, 10, 12])); // 18

空间优化：
我们可以用一维数组从后往前遍历：

function knapsack(C, w, v) {
  const n = w.length;
  const dp = new Array(C + 1).fill(0);
  
  for (let i = 0; i < n; i++) {
    // 注意：从后往前遍历，避免覆盖
    for (let j = C; j >= w[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  
  return dp[C];
}

3.6 例题六：最长公共子序列（LCS）

题目：
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

示例：

1
2
3

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。

解法：

第一步：定义 dp 数组的含义

dp[i][j]：text1[0…i-1] 和 text2[0…j-1] 的最长公共子序列长度

第二步：找出状态转移方程

如果 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
如果 text1[i-1] != text2[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

第三步：找出初始值

dp[i][0] = 0（text2 为空，公共子序列长度为 0）
dp[0][j] = 0（text1 为空，公共子序列长度为 0）

代码实现：

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  
  return dp[m][n];
}

console.log(longestCommonSubsequence("abcde", "ace")); // 3
console.log(longestCommonSubsequence("abc", "abc")); // 3
console.log(longestCommonSubsequence("abc", "def")); // 0

3.7 例题七：最大子数组和

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

示例：

1
2
3

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

解法：

第一步：定义 dp 数组的含义

dp[i]：以第 i 个元素结尾的最大子数组和

第二步：找出状态转移方程

对于第 i 个元素，有两种选择：
- 自己作为新子数组的起点：nums[i]
- 加入前面的子数组：dp[i-1] + nums[i]
所以：dp[i] = max(dp[i-1] + nums[i], nums[i])

第三步：找出初始值

dp[0] = nums[0]

代码实现：

function maxSubArray(nums) {
  const dp = new Array(nums.length);
  dp[0] = nums[0];
  let maxSum = dp[0];
  
  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    maxSum = Math.max(maxSum, dp[i]);
  }
  
  return maxSum;
}

console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])); // 6
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([5,4,-1,7,8])); // 23

空间优化：

function maxSubArray(nums) {
  let prev = nums[0];
  let maxSum = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    prev = Math.max(prev + nums[i], nums[i]);
    maxSum = Math.max(maxSum, prev);
  }
  
  return maxSum;
}

四、动态规划题型分类

4.1 按 dp 数组维度分类

类型	特点	例题
一维 DP	dp[i] 只依赖前面的状态	爬楼梯、打家劫舍、最大子数组和
二维 DP	dp[i][j] 依赖多个状态	不同路径、最长公共子序列、0-1 背包

4.2 按问题类型分类

类型一：线性 DP

问题沿着一维方向发展，状态转移方程通常是 dp[i] = f(dp[i-1], dp[i-2], ...)

特点：

一维数组
状态转移简单
容易空间优化

例题：

爬楼梯
斐波那契数列
打家劫舍
最大子数组和
最长递增子序列

类型二：二维 DP（网格问题）

问题在二维网格上进行，状态转移方程通常是 dp[i][j] = f(dp[i-1][j], dp[i][j-1])

特点：

二维数组
第一行和第一列通常需要初始化
方向：下、右、右下

例题：

不同路径
最小路径和
三角形最小路径和

类型三：双序列 DP

涉及两个序列/字符串的问题，状态转移方程通常比较两个序列的当前元素

特点：

二维数组 dp[m+1][n+1]
比较 s[i] 和 t[j]
相等或不相等有不同的转移方式

例题：

最长公共子序列（LCS）
编辑距离
最长回文子序列

类型四：背包问题

0-1 背包：

每个物品只能选或不选
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

完全背包：

每个物品可以选多次
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

多重背包：

每个物品有数量限制

例题：

0-1 背包
零钱兑换（完全背包）
分割等和子集（0-1 背包变体）

类型五：区间 DP

问题涉及区间 [i, j]，状态转移方程通常依赖更小的区间

特点：

dp[i][j] 表示区间 [i,j] 的解
先算小区间，再算大区间
按区间长度遍历

例题：

最长回文子串
戳气球
矩阵链乘法

五、动态规划解题技巧

5.1 空间优化技巧

很多时候我们可以把二维数组优化成一维数组，或者把一维数组优化成几个变量。

技巧一：一维数组代替二维数组（滚动数组）

当 dp[i][j] 只依赖 dp[i-1][...] 时，可以只用一维数组。

示例：0-1 背包

// 二维数组版本
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);

// 一维数组版本（从后往前遍历）
for (let j = C; j >= w[i]; j--) {
  dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}

技巧二：变量代替数组

当 dp[i] 只依赖 dp[i-1] 和 dp[i-2] 时，可以只用几个变量。

示例：爬楼梯

// 数组版本
dp[i] = dp[i-1] + dp[i-2];

// 变量版本
let prevPrev = dp[i-2];
let prev = dp[i-1];
let curr = prevPrev + prev;

5.2 如何找状态转移方程？

方法一：数学归纳法

先想 dp[n] 和 dp[n-1] 的关系
看能不能通过 dp[n-1] 推出 dp[n]
如果不行，再考虑 dp[n-2]

方法二：最后一步分析法

考虑最后一步发生了什么
倒推前一个状态
写出状态转移方程

示例：爬楼梯

最后一步：要么从 n-1 爬 1 级，要么从 n-2 爬 2 级
所以：dp[n] = dp[n-1] + dp[n-2]

方法三：选或不选

很多问题都是”选”或”不选”两种选择。

示例：打家劫舍

选第 i 间：dp[i-2] + nums[i]
不选第 i 间：dp[i-1]
所以：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

六、常见面试题总结

6.1 必须掌握的面试题

题目	类型	难度
爬楼梯	一维 DP	简单
斐波那契数	一维 DP	简单
最大子数组和	一维 DP	中等
打家劫舍	一维 DP	中等
最长递增子序列	一维 DP	中等
不同路径	二维 DP	中等
最小路径和	二维 DP	中等
最长公共子序列	双序列 DP	中等
零钱兑换	背包问题	中等
0-1 背包	背包问题	中等

6.2 面试回答要点

Q：什么是动态规划？

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。核心思想是利用历史记录避免重复计算。

Q：动态规划的三步骤是什么？

定义 dp 数组元素的含义
找出状态转移方程
找出初始值

Q：动态规划和贪心的区别？

贪心：每一步都做出局部最优选择，希望最终得到全局最优
动态规划：会考虑所有可能的选择，利用历史记录避免重复计算

Q：动态规划和递归的区别？

递归：自顶向下，可能有大量重复计算
动态规划：自底向上，利用历史记录避免重复计算

七、总结

7.1 核心知识点回顾

知识点	关键内容
核心思想	利用历史记录避免重复计算
三步骤	定义 dp 含义 → 找状态转移方程 → 找初始值
题型分类	线性 DP、二维 DP、双序列 DP、背包问题、区间 DP
空间优化	滚动数组、变量代替数组

7.2 学习建议

从简单题入手：先爬楼梯、斐波那契，理解三步骤
多画图推导：在纸上画出 dp 数组的变化过程
总结题型：把题目分类，找出每种题型的解题套路
注意空间优化：写完代码后想想能不能优化空间
多练习：动态规划需要大量练习才能熟练掌握

记住：动态规划的关键是定义好 dp 数组的含义！只要这一步想清楚了，后面就迎刃而解了！