在算法世界中，动态规划（Dynamic Programming，简称 DP）是一种「化繁为简」的智慧 —— 它将复杂问题拆解为重叠的子问题，通过存储子问题的最优解，避免重复计算，最终高效得到全局最优解。这种思想广泛应用于最优路径、资源分配、序列匹配等场景，也是面试中仅次于贪心的高频考点。

本文将从「核心原理→适用条件→经典例题（含空间优化）→避坑指南」四个维度，帮你彻底打通动态规划的任督二脉，看完直接上手刷题！

一、动态规划是什么？核心思想拆解

1. 定义

动态规划是指在解决问题时，将问题分解为若干个重叠的子问题，通过记录子问题的最优解（存储在「DP 表」中），避免重复计算，最终递推得到原问题的最优解。

2. 核心特点

重叠子问题：原问题的解依赖多个子问题的解，且子问题之间存在重复（比如斐波那契数列中，f (5)=f (4)+f (3)，f (4)=f (3)+f (2)，f (3) 被重复计算）；

最优子结构：原问题的最优解包含子问题的最优解（比如最短路径中，A→C 的最短路径一定包含 A→B 的最短路径）；

无后效性：子问题的解一旦确定，就不会被后续决策影响（比如确定 f (3) 后，计算 f (4) 时只需使用 f (3) 的结果，无需关心 f (3) 是如何得到的）。

3. 动态规划 vs 贪心算法（关键区别）

很多人会混淆 DP 和贪心，用一张表明确区分：

特性

动态规划

贪心算法

核心思想

子问题重叠 + 最优子结构，存储子问题解

局部最优→全局最优，不存储子问题解

适用条件

重叠子问题、最优子结构

贪心选择性质、最优子结构

决策方式

自底向上 / 自顶向下递推

一步到位的局部最优决策

典型场景

0-1 背包、最长子序列、最短路径

找零、活动选择、区间覆盖

4. 动态规划的核心三要素

解决任何 DP 问题，都离不开这三个核心步骤：

状态定义：确定 DP 表的含义（比如dp[i]代表什么）；

转移方程：如何通过子问题的解推导当前问题的解（比如dp[i] = dp[i-1] + dp[i-2]）；

初始条件 + 边界处理：确定 DP 表的起始值（比如dp[0]=0, dp[1]=1）和边界约束（比如数组越界、无效状态）。

二、动态规划的适用条件（别用错场景！）

并非所有问题都适合用 DP，必须满足两个核心条件：

重叠子问题：子问题重复出现，否则存储子问题解毫无意义（比如排序问题无重叠子问题，无需 DP）；

最优子结构：原问题的最优解可由子问题的最优解推导而来（比如「最长递增子序列」中，以第 i 个元素结尾的最长子序列，可由前 i-1 个元素的最长子序列推导）。

如何判断一个问题能否用 DP？

答：先看是否有重叠子问题（比如递归解法会重复计算），再验证是否满足最优子结构（举例子看子问题最优是否能推导全局最优）。

三、经典例题实战（含 Python 代码 + 优化技巧）

例题 1：斐波那契数列（入门 DP，理解重叠子问题）

问题描述

求斐波那契数列的第 n 项（n≥0），数列定义：f (0)=0，f (1)=1，f (n)=f (n-1)+f (n-2)（n≥2）。

问题分析

递归解法的问题：会重复计算大量子问题（比如 f (5) 需要 f (4) 和 f (3)，f (4) 又需要 f (3) 和 f (2)，f (3) 被计算 2 次），时间复杂度 O (2ⁿ)；

DP 解法：用数组存储已计算的子问题解，时间复杂度优化到 O (n)，空间可进一步优化到 O (1)。

动态规划思路

状态定义：dp[i] 表示斐波那契数列的第 i 项；

转移方程：dp[i] = dp[i-1] + dp[i-2]（i≥2）；

初始条件：dp[0] = 0，dp[1] = 1；

边界处理：n=0 或 n=1 时直接返回初始值。

代码实现（基础版 + 空间优化版）

# 基础版：空间复杂度O(n)

def fib_base(n):

if n <= 1:

return n

# 初始化DP表

dp = [0] * (n+1)

dp[1] = 1

# 递推计算

for i in range(2, n+1):

dp[i] = dp[i-1] + dp[i-2]

return dp[n]

# 优化版：空间复杂度O(1)（只存储前两个状态）

def fib_optimized(n):

if n <= 1:

return n

a, b = 0, 1 # a=dp[i-2], b=dp[i-1]

for _ in range(2, n+1):

a, b = b, a + b # 滚动更新

return b

# 测试用例

print("斐波那契第10项（基础版）：", fib_base(10)) # 输出：55

print("斐波那契第10项（优化版）：", fib_optimized(10)) # 输出：55

复杂度分析

基础版：时间 O (n)，空间 O (n)；

优化版：时间 O (n)，空间 O (1)（核心：用变量滚动存储，无需完整 DP 表）。

例题 2：爬楼梯（入门进阶，理解状态转移）

问题描述

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

动态规划思路

状态定义：dp[i] 表示爬到第 i 阶的不同方式数；

转移方程：爬到第 i 阶，只能从第 i-1 阶（爬 1 步）或第 i-2 阶（爬 2 步）过来，因此 dp[i] = dp[i-1] + dp[i-2]；

初始条件：dp[0] = 1（0 阶只有 1 种方式：不爬），dp[1] = 1（1 阶只有 1 种方式：爬 1 步）；

边界处理：n≥0，无负数阶数。

代码实现（空间优化版）

def climb_stairs(n):

if n <= 1:

return 1

a, b = 1, 1 # a=dp[i-2], b=dp[i-1]

for _ in range(2, n+1):

a, b = b, a + b

return b

# 测试用例

print("爬5阶楼梯的方式数：", climb_stairs(5)) # 输出：8（1+1+1+1+1、1+1+2、1+2+1、2+1+1、2+2+1、2+1+2、1+2+2、2+2）

关键说明

本题本质是斐波那契数列的变种，核心是找到状态转移的逻辑；

空间优化的核心：当dp[i]只依赖前 k 个状态时，可用 k 个变量滚动存储，无需完整 DP 表。

例题 3：0-1 背包问题（经典 DP，理解二维 DP 表）

问题描述

有 n 件物品，每件物品的重量为weight[i]，价值为value[i]，背包的最大容量为capacity。每件物品只能选或不选（0-1），求背包能装下的最大价值。

问题分析

贪心算法不适用：比如物品 [3,4]、价值 [5,6]、背包容量 5，贪心选价值 / 重量比高的 4（价值 6），但最优是选 3（价值 5）+ 剩余 2 装不下，总价值 5？不对，正确反例：物品 [2,3,4]、价值 [3,4,5]、背包容量 5，贪心选 4（价值 5），最优是 2+3（价值 7）；

DP 解法：用二维 DP 表记录「前 i 件物品 + 容量 j」的最大价值，避免重复计算。

动态规划思路

状态定义：dp[i][j] 表示前 i 件物品（0~i-1）放入容量为 j 的背包，能获得的最大价值；

转移方程：

不选第 i-1 件物品：dp[i][j] = dp[i-1][j]（继承前 i-1 件的最大价值）；

选第 i-1 件物品（前提：j≥weight [i-1]）：dp[i][j] = dp[i-1][j - weight[i-1]] + value[i-1]（前 i-1 件物品放入容量 j-weight [i-1] 的背包，再加上当前物品的价值）；

最终取两者最大值：dp[i][j] = max(不选, 选)；

初始条件：dp[0][j] = 0（0 件物品，价值为 0），dp[i][0] = 0（容量为 0，价值为 0）；

边界处理：物品重量不能超过背包容量。

代码实现（基础二维版 + 空间优化一维版）

# 基础版：二维DP表，空间复杂度O(n*capacity)

def knapsack_01_base(weight, value, capacity):

n = len(weight)

# 初始化DP表：(n+1)行（物品数），(capacity+1)列（容量）

dp = [[0]*(capacity+1) for _ in range(n+1)]

# 递推计算

for i in range(1, n+1):

for j in range(1, capacity+1):

# 第i-1件物品的重量超过当前容量j，无法选择

if weight[i-1] > j:

dp[i][j] = dp[i-1][j]

else:

# 选或不选，取最大值

dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1])

return dp[n][capacity]

# 优化版：一维DP表，空间复杂度O(capacity)（逆序遍历避免覆盖）

def knapsack_01_optimized(weight, value, capacity):

n = len(weight)

# 初始化一维DP表：容量从0到capacity

dp = [0]*(capacity+1)

# 递推计算（逆序遍历容量）

for i in range(n):

# 逆序遍历：避免重复选择同一物品（0-1背包只能选一次）

for j in range(capacity, weight[i]-1, -1):

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

return dp[capacity]

# 测试用例

weight = [2,3,4,5]

value = [3,4,5,6]

capacity = 8

print("0-1背包最大价值（二维版）：", knapsack_01_base(weight, value, capacity)) # 输出：10（3+7？不，正确是2+3+3？哦计算：weight[0]=2(3)+weight[1]=3(4)+weight[2]=4(5) → 总重9>8；最优是weight[0]=2(3)+weight[3]=5(6) → 总重7，价值9？不对，代码运行结果是10：weight[1]=3(4)+weight[3]=5(6) → 总重8，价值10！）

print("0-1背包最大价值（一维版）：", knapsack_01_optimized(weight, value, capacity)) # 输出：10

复杂度分析

基础版：时间 O (ncapacity)，空间 O (ncapacity)；

优化版：时间 O (n*capacity)，空间 O (capacity)（核心：逆序遍历容量，避免覆盖未使用的子问题解）。

例题 4：最长递增子序列（LIS，高频面试题）

问题描述

给定一个整数数组nums，求其中最长严格递增子序列的长度（子序列不要求连续）。

动态规划思路

状态定义：dp[i] 表示以nums[i]结尾的最长递增子序列的长度；

转移方程：遍历前 i 个元素，若nums[j] < nums[i]（j < i），则dp[i] = max(dp[i], dp[j] + 1)（以 nums [j] 结尾的子序列加上 nums [i]，形成更长的递增子序列）；

初始条件：dp[i] = 1（每个元素自身是长度为 1 的子序列）；

边界处理：数组为空时返回 0。

代码实现（基础版 + 优化思路）

# 基础版：时间O(n²)，空间O(n)

def length_of_lis_base(nums):

if not nums:

return 0

n = len(nums)

dp = [1]*n # 初始化每个元素的最长子序列长度为1

max_len = 1 # 记录全局最大值

for i in range(1, n):

# 遍历前i个元素，寻找比nums[i]小的元素

for j in range(i):

if nums[j] < nums[i]:

dp[i] = max(dp[i], dp[j] + 1)

# 更新全局最大值

if dp[i] > max_len:

max_len = dp[i]

return max_len

# 优化版：时间O(nlogn)（用二分查找优化内层循环，非DP思路，拓展学习）

def length_of_lis_optimized(nums):

tails = [] # tails[i]表示长度为i+1的递增子序列的最小尾部元素

for num in nums:

# 二分查找插入位置

left, right = 0, len(tails)

while left < right:

mid = (left + right) // 2

if tails[mid] < num:

left = mid + 1

else:

right = mid

# 插入当前元素

if left == len(tails):

tails.append(num)

else:

tails[left] = num

return len(tails)

# 测试用例

nums = [10,9,2,5,3,7,101,18]

print("最长递增子序列长度（基础版）：", length_of_lis_base(nums)) # 输出：4（2→3→7→101 或 2→5→7→101 等）

print("最长递增子序列长度（优化版）：", length_of_lis_optimized(nums)) # 输出：4

关键说明

基础版是标准 DP 解法，适合理解 LIS 的核心逻辑；

优化版用二分查找将时间复杂度从 O (n²) 降到 O (nlogn)，是面试中的最优解法（虽非 DP，但属于 LIS 的必学拓展）。

四、动态规划的常见误区与避坑指南

误区 1：状态定义模糊（最致命！）

比如 0-1 背包问题中，若错误定义dp[i][j]为「第 i 件物品放入容量 j 的背包的价值」，会导致转移方程无法推导。

避坑：状态定义要明确「范围 + 约束 + 目标」，比如「前 i 件物品 + 容量 j + 最大价值」。

误区 2：转移方程遗漏边界条件

比如爬楼梯问题中，忘记dp[0] = 1（0 阶的情况），会导致 n=2 时计算错误（dp [2] = dp [1] + dp [0] = 1+1=2，正确）。

避坑：先列出前 3~5 个状态的具体值，验证转移方程是否正确。

误区 3：空间未优化，导致内存超限

比如 0-1 背包问题中，当 capacity=1e4 时，二维 DP 表会占用 1e8 + 的空间，导致内存溢出。

避坑：观察转移方程依赖的前序状态，若只依赖前一行 / 前 k 个状态，可改用滚动数组或变量优化。

误区 4：混淆「子序列」和「子数组」

比如最长递增子序列（子序列不连续）和最长连续递增子数组（子数组连续）的 DP 状态定义不同，前者dp[i]依赖所有 j

避坑：明确问题要求，子序列可跳跃，子数组必须连续。

五、总结与拓展

核心总结

动态规划的本质：重叠子问题 + 最优子结构，核心是「存储子问题解，避免重复计算」；

解题四步法：① 定义状态（明确范围 + 约束 + 目标）；② 推导转移方程（子问题如何递推）；③ 初始化 DP 表（初始条件）；④ 处理边界 + 迭代计算；

优化技巧：空间优化（滚动数组 / 变量）、时间优化（二分查找等，视问题而定）。

拓展学习

进阶例题：最长公共子序列（LCS）、编辑距离、打家劫舍系列、股票买卖系列；

专项训练：线性 DP（爬楼梯、LIS）、二维 DP（0-1 背包、LCS）、区间 DP（石子合并）、状态压缩 DP（旅行商问题）；

刷题建议：LeetCode 53（最大子数组和）、LeetCode 62（不同路径）、LeetCode 198（打家劫舍）、LeetCode 300（最长递增子序列）。

如果本文对你有帮助，欢迎点赞、收藏、转发～ 若有疑问或想讨论更多动态规划的问题（比如某道题的 DP 思路），欢迎在评论区留言！