第十一篇：动态规划（DP）（上）
前言
动态规划（Dynamic Programming，DP）是算法设计中解决最优子结构问题的重要技巧，被广泛应用于路径优化、资源分配、序列处理等领域。本篇将系统阐述动态规划的核心概念、实现技巧与典型案例，帮助你从零到一掌握 DP 思维。
一、动态规划基础
1.1 什么是动态规划？
动态规划是一种将复杂问题分解为相互重叠子问题，通过保存子问题结果避免重复计算，从而提高效率的算法设计方法。它结合了分治思想与记忆化技术，适用于具有最优子结构和重复子问题的情景。
1.2 动态规划与分治的区别与联系
-
分治（Divide & Conquer）：将问题拆分为独立子问题，递归求解后合并，子问题之间无交集。
-
动态规划：将问题拆分为相互重叠的子问题，通过备忘录或表格存储子问题结果，避免重复计算。
联系：分治的分解思想与 DP 的状态转移相似；区别在于分治不复用子问题结果，DP 强调子问题复用。
1.3 动态规划三要素
-
状态定义（State）：明确
dp[i]、dp[i][j]等状态代表含义。 -
状态转移方程（Transition）：根据子问题推导出
dp之间的关系。 -
边界条件（Base Case）：初始化
dp数组或表第一行/列。
1.4 自顶向下 vs 自底向上
-
自顶向下（Top-Down）：递归 + 记忆化，代码直观易写，但有栈开销。
-
自底向上（Bottom-Up）：循环填表，省去函数调用，常用迭代实现。
示例：斐波那契数列两种实现对比。
二、线性 DP 问题
2.1 斐波那契数列 & 爬楼梯
问题
-
斐波那契：
F(n)=F(n-1)+F(n-2)。 -
爬楼梯：每次可爬 1 或 2 级，求到第 n 级的方案数，等同 Fibonacci。
实现
// 自底向上
int fib(int n) {if (n <= 1) return n;int a=0, b=1;for(int i=2;i<=n;i++){int c=a+b;a=b; b=c;}return b;
}
时间 O(n)，空间 O(1)。
2.2 打家劫舍（House Robber I/II）
问题定义
-
I：线性房屋，不能抢相邻两家。
-
II：环形房屋，首尾相连。
转移方程
-
dp[i]=max(dp[i-1], dp[i-2]+nums[i])
实现
int rob(int[] nums) {int n=nums.length;int[] dp=new int[n+1];dp[0]=0; dp[1]=nums[0];for(int i=2;i<=n;i++)dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i-1]);return dp[n];
}
环形拆两次求解。空间可 O(1)。
2.3 股票买卖系列（I/II/III/IV）
I：一笔交易
-
minPrice与maxProfit。
II：多笔交易
-
贪心
sum += max(0, price[i]-price[i-1])。
III：两笔交易
-
dp[i][k][0/1]状态机或两次分段 DP。
IV：最多 k 笔交易
-
通用状态机
dp[i][j][0/1]，时间 O(nk)。
三、最大子序和（Maximum Subarray）
3.1 问题
给定整数数组，找出具有最大和的连续子数组。
3.2 转移方程
dp[i]=max(dp[i-1]+nums[i], nums[i])
int maxSubArray(int[] nums) {int dp=nums[0], max=nums[0];for(int i=1;i<nums.length;i++){dp=Math.max(dp+nums[i], nums[i]);max=Math.max(max, dp);}return max;
}
时间 O(n)，空间 O(1)。
四、区间 DP 与区间型问题
区间 DP 适用于区间最优问题，如戳气球、最优二叉搜索树、回文分割。
4.1 区间 DP 模板
for (int len=2;len<=n;len++)for (int i=0;i+len<=n;i++) {int j=i+len-1;dp[i][j]=... // 根据 k 遍历 [i,j]}
4.2 戳气球（Burst Balloons）
状态 dp[i][j] 表示戳破 (i,j) 区间内所有气球的最大硬币，转移：
for k in [i+1,j-1]:dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j])
4.3 最优二叉搜索树（Optimal BST）
概率加权区间 DP，类似戳气球。
4.4 回文子串 / 分割回文串
-
isPal[i][j]预处理 O(n²)。 -
dp[i]=min(dp[j]+1) if isPal[j+1][i]。
五、本篇小结
-
理解状态定义与状态转移方程是 DP 的核心。
-
掌握自顶向下与自底向上的实现方式，兼顾可读性与性能。
-
线性 DP 案例涉及斐波那契、打家劫舍与股票买卖，练习状态机思想。
-
区间 DP 是一类独特范式，常用于序列分割与组合最优问题。