第25篇-动态规划入门-从爬楼梯到经典状态转移

概述

上一篇我们学习了贪心算法，核心是局部最优能否推出全局最优。

这一篇我们进入动态规划，也就是常说的DP。

动态规划是很多初学者的难点，因为它看起来不像排序、二分那样“有固定套路”，而更像是在做一件事：

把一个问题拆成很多个小问题，再把小问题的答案存起来

它最适合处理的就是这类问题：

• 有重叠子问题
• 有最优子结构
• 需要求最值、方案数、可达性
• 状态之间可以转移

典型题包括：

• 爬楼梯
• 斐波那契数列
• 打家劫舍
• 最长递增子序列
• 背包问题

本篇先不急着上复杂题。
我们先把动态规划最核心的四个词讲清楚：

状态、定义、转移、初始化

学完这篇，你应该能看懂最基础的 DP 题，并能自己写出一维 DP 的标准模板。

核心概念：动态规划到底是什么

动态规划的核心思想是：

把原问题拆成若干子问题，保存子问题答案，避免重复计算

为什么要保存答案

如果你直接用递归去做很多问题，会发现同一个子问题被重复算很多次。

例如斐波那契数列：

f(n) = f(n - 1) + f(n - 2)

如果直接递归，f(n - 1)和f(n - 2)里又会继续算出很多重叠内容。

这就导致大量重复计算。

DP 的作用就是：

已经算过的子问题答案，直接记录下来，下次不用再算

动态规划三要素

通常可以这样理解：

1. 状态：我用什么变量表示一个子问题
2. 转移：当前状态怎么从之前状态推出来
3. 初始化：最开始的已知答案是什么

如果这三件事想清楚了，DP 就有了轮廓。

DP 的本质是记住子问题答案，并用它们推导更大的问题。

先从最简单的题开始：爬楼梯

题目：

一共有n阶楼梯，每次可以爬1阶或2阶，问有多少种不同方法爬到第n阶。

这是 DP 最经典的入门题之一。

先找状态

我们定义：

dp[i] 表示爬到第 i 阶楼梯的方法数

这就是状态定义。

再找转移

到达第i阶楼梯，最后一步只有两种可能：

• 从i - 1阶爬1步上来
• 从i - 2阶爬2步上来

所以：

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

再找初始化

已知：

• dp[0] = 1
• dp[1] = 1

这里dp[0] = 1的含义是“站在原地有一种方式”。

Java 代码实现

classSolution{publicintclimbStairs(intn){if(n<=1){return1;}int[]dp=newint[n+1];dp[0]=1;dp[1]=1;for(inti=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}}

空间优化状态压缩

因为转移只依赖前两个状态，所以不需要整个数组。

classSolution{publicintclimbStairs(intn){if(n<=1){return1;}inta=1;intb=1;for(inti=2;i<=n;i++){intc=a+b;a=b;b=c;}returnb;}}

爬楼梯是最基础的一维 DP，状态是“到第几阶的方法数”。

斐波那契数列：最直接的状态转移模型

斐波那契数列和爬楼梯几乎是同一个模型。

题目通常写成：

计算第n个斐波那契数。

定义：

f[0] = 0 f[1] = 1 f[i] = f[i - 1] + f[i - 2]

Java 代码实现

classSolution{publicintfib(intn){if(n<=1){returnn;}inta=0;intb=1;for(inti=2;i<=n;i++){intc=a+b;a=b;b=c;}returnb;}}

为什么先学斐波那契

因为它把 DP 的核心逻辑暴露得非常清楚：

• 状态是什么
• 状态如何转移
• 初始条件是什么

它是很多 DP 题的最小模型。

斐波那契是 DP 入门最干净的模板，状态转移几乎一眼可见。

动态规划的标准思考流程

做 DP 题时，不要先急着写代码。
先按下面步骤想：

第一步：定义状态

问自己：

我用什么变量表示一个子问题？

例如：

• dp[i]表示前i个房子能偷到的最大金额
• dp[i]表示以第i个数结尾的最长递增子序列长度
• dp[i][j]表示前i个物品、容量j时的最优值

第二步：找状态转移

问自己：

当前状态能从哪些以前的状态推出来？

这一步通常是最关键的。

第三步：确定初始值

问自己：

最小的子问题答案是什么？

第四步：确定遍历顺序

问自己：

我计算当前状态时，依赖的状态是不是都已经算过了？

如果依赖前面的状态，就要先算前面的。

第五步：思考答案在哪里

问自己：

最终答案是 dp[n]，还是 dp 数组里的最大值，还是多个状态的综合？

先定义状态，再写转移，再填初始化，最后确定遍历顺序和答案位置。

题型一：最简单的一维 DP

一维 DP 往往长这样：

dp[i] 只依赖前面的一个或几个状态

常见一维 DP 模板

int[]dp=newint[n+1];dp[0]=baseValue;for(inti=1;i<=n;i++){dp[i]=transition(dp[i-1],dp[i-2],...);}returndp[n];

典型场景

• 台阶问题
• 线性最优值
• 计数类问题
• 以位置为状态的问题

例子：简单计数型递推

如果一个状态只依赖前两个状态，就可以直接这样写：

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

一维 DP 的特点是状态顺着数组推进，通常只依赖前面少数几个位置。

题型二：最大子数组和的状态设计

题目：

给定一个整数数组，找出具有最大和的连续子数组。

这是后面线性 DP 的经典题，这里先提前感受一下状态设计。

状态定义

定义：

dp[i] 表示以 nums[i] 结尾的最大子数组和

这个定义很关键。
它不是“前 i 个数的最大和”，而是“以 i 结尾”。

为什么这么定义？

因为当前子数组要么接在前一个子数组后面，要么从当前元素重新开始。

转移方程

dp[i] = max(dp[i - 1] + nums[i], nums[i])

含义是：

• 如果前面的和对我有帮助，就接上
• 如果前面的和是负数，直接从自己重新开始

Java 代码实现

classSolution{publicintmaxSubArray(int[]nums){intn=nums.length;int[]dp=newint[n];dp[0]=nums[0];intans=dp[0];for(inti=1;i<n;i++){dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);ans=Math.max(ans,dp[i]);}returnans;}}

为什么答案不是dp[n - 1]

因为最大子数组可能结束在任何位置。
所以最终答案应该是整个dp数组里的最大值。

空间优化状态压缩

只依赖前一个状态时，可以压缩成两个变量：

classSolution{publicintmaxSubArray(int[]nums){intcur=nums[0];intans=nums[0];for(inti=1;i<nums.length;i++){cur=Math.max(cur+nums[i],nums[i]);ans=Math.max(ans,cur);}returnans;}}

状态一旦定义成“以当前位置结尾”，转移就会非常自然。

题型三：打家劫舍的基础模型

题目：

一排房子，每个房子里有一定金额，不能偷相邻房子，求能偷到的最大金额。

这是线性 DP 的经典题。

状态定义

定义：

dp[i] 表示前 i 个房子能偷到的最大金额

状态转移

对第i个房子，有两种选择：

• 不偷第i个房子：dp[i - 1]
• 偷第i个房子：dp[i - 2] + nums[i]

所以：

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

Java 代码实现

classSolution{publicintrob(int[]nums){intn=nums.length;if(n==1){returnnums[0];}int[]dp=newint[n];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(inti=2;i<n;i++){dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);}returndp[n-1];}}

为什么这题适合 DP

因为当前房子是否能偷，取决于前一个房子偷没偷。
这正是“状态之间存在依赖”的典型情况。

线性 DP 的关键是定义“前 i 个位置”的最优值，并用“偷与不偷”推状态。

题型四：DP 题的遍历顺序

很多人写 DP 时，状态和转移都想出来了，但代码还是错。
常见原因是：

遍历顺序不对

一维 DP 一般怎么遍历

如果dp[i]依赖dp[i - 1]或dp[i - 2]，那么通常要从小到大遍历。

例如：

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

为什么不能乱序

因为你在计算dp[i]时，依赖的前置状态必须已经算出来。

如果依赖还没准备好，结果就不可信。

一个简单记法

依赖谁，就先算谁

DP 不是随便循环，必须保证当前状态依赖的状态已经提前算完。

常见坑点：动态规划最容易错在哪里

1. 状态定义不清楚

很多 DP 错误不是转移错，而是状态一开始就定义偏了。

状态定义必须清楚回答：

dp[i] 到底表示什么？

2. 状态定义太大或太小

如果状态定义太粗，转移会丢信息。
如果状态定义太细，复杂度会爆炸。

3. 初始化漏掉边界

DP 很多错都出在：

• dp[0]
• dp[1]
• 空数组
• 单元素数组

4. 遍历顺序不匹配转移

如果当前状态依赖前面的状态，就必须先算前面。

5. 把“前 i 个”写成“以 i 结尾”

这两个状态差别很大。

例如最大子数组和里，如果你定义成“前 i 个的最大和”，转移就会很难写。
定义成“以 i 结尾”就自然很多。

6. 忘记最终答案不一定在dp[n]

有些题答案是dp[n]，有些题答案是max(dp)，还有些题答案是多个状态取最优。

复杂度分析：DP 的代价从哪里来

动态规划通常把原本指数级的重复递归，降成多项式级别。

爬楼梯

• 时间复杂度：O(n)
• 空间复杂度：O(n)，可优化到O(1)

斐波那契

• 时间复杂度：O(n)
• 空间复杂度：O(1)

最大子数组和

• 时间复杂度：O(n)
• 空间复杂度：O(n)，可优化到O(1)

打家劫舍

• 时间复杂度：O(n)
• 空间复杂度：O(n)，可优化到O(1)

DP 的关键不只是快，而是：

把重复子问题变成一次计算

模板总结：最基础的一维 DP 怎么写

可以先记住这个通用框架：

// 1. 定义 dpint[]dp=newint[n+1];// 2. 初始化dp[0]=baseValue;// 3. 状态转移for(inti=1;i<=n;i++){dp[i]=transition(dp[i-1],dp[i-2],...);}// 4. 返回答案returndp[n];

如果只能记一句：

先定义 dp[i] 的含义，再想它怎么由前面的状态推出来

总结

动态规划是算法里最重要的体系之一。
它不是死记硬背公式，而是先把问题拆成可重复利用的小问题。

你可以重点记住下面几句话：

• DP 的本质是保存子问题答案，避免重复计算
• 最重要的四件事是状态、转移、初始化、遍历顺序
• 爬楼梯和斐波那契是最基础的一维 DP
• 最大子数组和要把状态定义成“以当前位置结尾”
• 打家劫舍体现了“选与不选”的典型状态转移
• 写 DP 前一定先说清dp[i]表示什么
• DP 题最常见的错误是状态定义不清和初始化遗漏