DP 复习笔记

一、动态规划的基本方法

遇到这类题目，先按下面顺序想：

1. 状态是什么：dp[i] 或 dp[i][j] 表示什么结果，必须说清楚下标的含义。
2. 最后一步怎么来：当前状态通常由前面一个或几个状态转移而来。
3. 边界是什么：例如第一行、第一列、第一项，以及空前缀 s[0]。
4. 答案在哪：有些题答案是 dp[n]，有些题要在所有 dp[i] 中取最大值。
5. 计算顺序：转移依赖谁，就先计算谁。线性 DP 从前往后，二维网格通常按行、列从小到大。

DP 不是把所有方案都存下来，而是只保存“到达某个状态时的最好结果”。

---

二、数塔问题：从相邻位置转移

题型识别

数塔从上到下或从下到上走，每次只能到相邻位置，要求路径和最大。当前位置只可能从上一层的两个位置到达。

状态与转移

dp[i][j] 表示从顶层走到第 i 层第 j 个数时，能得到的最大和。

当 1<j<i 时：

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

边缘位置只有一个来源：第一列只能从上一层第一列来，第 i 列只能从上一层第 i-1 列来。最后一层的最大值就是答案。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
int n,a[N][N],dp[N][N],ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++) cin>>a[i][j];
	}
	dp[1][1]=a[1][1];
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(j==1) dp[i][j]=dp[i-1][j]+a[i][j];
			else if(j==i) dp[i][j]=dp[i-1][j-1]+a[i][j];
			else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
		}
	}
	for(int j=1;j<=n;j++) ans=max(ans,dp[n][j]);
	cout<<ans<<"\n";
	return 0;
}

易错点

• 第 i 层只有 i 个数，循环不能写到 n。
• 不能把边缘位置当成有两个来源，否则会用到不合法的位置。
• 答案是最后一层所有位置的最大值，不一定是最后一层最右边或最左边。

---

三、摘花生：网格路径 DP

题型识别

从左上角走到右下角，每次只能向右或向下。到达一个格子时，只有“从上面来”和“从左边来”两种情况。

状态与转移

dp[i][j] 表示走到第 i 行第 j 列时最多收集的花生数。

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

每组数据都要重新计算。由于数据非负，初始的零值不会影响结果；写出明确的边界更不容易出错。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
int t,n,m,a[N][N],dp[N][N];
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
				dp[i][j]=0;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i==1&&j==1) dp[i][j]=a[i][j];
				else if(i==1) dp[i][j]=dp[i][j-1]+a[i][j];
				else if(j==1) dp[i][j]=dp[i-1][j]+a[i][j];
				else dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
			}
		}
		cout<<dp[n][m]<<"\n";
	}
	return 0;
}

易错点

• 输入有多组数据，t 每减少一次就要完整处理一张网格。
• 第一行和第一列只有一个方向能到达，不能直接套两个转移。
• 读入新数据时，数组下标和 n,m 要对应当前这一组。

---

四、大盗阿福：不能选相邻元素

题型识别

每家店有一个金额，不能同时选择相邻的两家，求能得到的最大金额。这是最典型的“不相邻选取”线性 DP。

状态与转移

dp[i] 表示只看前 i 家店时的最大金额。

• 不选第 i 家：dp[i-1]
• 选第 i 家：不能选第 i-1 家，为 dp[i-2]+a[i]

所以：

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

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100000+5;
int t,n,a[N],dp[N];
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i],dp[i]=0;
		dp[0]=0;
		if(n>=1) dp[1]=a[1];
		for(int i=2;i<=n;i++) dp[i]=max(dp[i-1],dp[i-2]+a[i]);
		cout<<dp[n]<<"\n";
	}
	return 0;
}

易错点

• 选第 i 家时，前面只能接 dp[i-2]，不能接 dp[i-1]。
• n=1 时不能直接访问 a[2] 或把 dp[1] 漏掉。
• 多组数据要重新读入并重新计算，不能把上一组的状态带到下一组。

---

五、最大子段和：连续区间的取舍

题型识别

要求一段连续数字的最大和。关键是考虑“以第 i 个数结尾”的最佳子段：它要么从 a[i] 重新开始，要么接在以 i-1 结尾的子段后面。

状态与转移

dp[i] 表示必须以 a[i] 结尾的最大连续子段和。

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

最终答案要在所有 dp[i] 中取最大值，不能只输出 dp[n]，因为最优子段可能提前结束。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000000+5;
int n,a[N],dp[N],ans=-1e18;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		dp[i]=max(a[i],dp[i-1]+a[i]);
		ans=max(ans,dp[i]);
	}
	cout<<ans<<"\n";
	return 0;
}

易错点

• dp[i] 和“前 i 个数的答案”不是一回事；前者必须以 i 结尾。
• 不能只输出 dp[n]。
• 如果题目没有保证存在正数，答案初值不能写成 0，否则全负数时会错。

---

六、最大子阵和：二维问题压成一维

题型识别

子矩阵必须是连续的行和连续的列。枚举子矩阵的上边界和下边界后，固定行范围，把每一列在这几行中的和累加起来，就变成了一个一维最大子段和问题。

做法

固定上边界 top，让下边界 bottom 从 top 往下移动：

1. sum[j] 表示第 top 行到第 bottom 行第 j 列的总和。
2. 对 sum[1..n] 做一次最大子段和，得到这组行范围的最优列区间。
3. 枚举所有 top,bottom，取最大答案。

复杂度为 $O(n^3)$，适合本题 $n\le 500$ 的范围。

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int n,a[N][N],sum[N],ans=-1e18;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cin>>a[i][j];
	}
	for(int top=1;top<=n;top++){
		for(int j=1;j<=n;j++) sum[j]=0;
		for(int bottom=top;bottom<=n;bottom++){
			for(int j=1;j<=n;j++) sum[j]+=a[bottom][j];
			int cur=sum[1];
			ans=max(ans,cur);
			for(int j=2;j<=n;j++){
				cur=max(sum[j],cur+sum[j]);
				ans=max(ans,cur);
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}

易错点

• sum[j] 必须在每个新的 top 开始时清零。
• bottom 不能小于 top，否则行范围不合法。
• 不能只找每一列的最大值；列必须连续，所以最后仍要做一次最大子段和。
• 所有数都可能为负，cur 和 ans 不能从 0 开始。

---

七、长度至少为 $k$ 的最大子段和：前缀和加最小值

题型识别

普通最大子段和不限制长度，这道题要求长度至少为 $k$。设子段为 $[j+1,i]$，它的和为：

s[i] - s[j]

其中 s[i] 是前 i 个数的前缀和。长度条件 i-j>=k 等价于 j<=i-k。

状态与转移

对于每个右端点 i，要让 s[i]-s[j] 最大，就要在 s[0]...s[i-k] 中找最小值。

令 minn[i] 表示 s[0]...s[i] 的最小值，则：

答案 = max(答案, s[i] - minn[i-k])   （i 从 k 枚举到 n）

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000000+5;
int n,k,a[N],s[N],minn[N],ans=-1e18;
signed main(){
	cin>>n>>k;
	minn[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		minn[i]=min(minn[i-1],s[i]);
	}
	for(int i=k;i<=n;i++) ans=max(ans,s[i]-minn[i-k]);
	cout<<ans<<"\n";
	return 0;
}

易错点

• i 必须从 k 开始，不能在 i<k 时访问 minn[i-k]，否则会出现负下标。
• minn[0] 对应空前缀 s[0]=0，不能漏掉长度恰好为 k 的子段。
• 维护的是“前面允许作为左端点的所有前缀和的最小值”，不是只比较 s[i-1]。
• 这道题的前缀和可能很大，使用 long long 更稳妥。

---

八、最后统一检查

提交前按这张清单检查：

• dp[i]、dp[i][j] 的含义能否用一句话说清楚？
• 转移是否只使用已经计算好的状态？
• 第一项、第一行、第一列、空前缀是否处理？
• 多组数据是否重新读入并重新计算？
• 答案是最后一个状态，还是所有状态中的最大值？
• 是否有负下标、数组越界、答案初值为 0 等问题？

今天的题目可以按这个顺序复习：数塔 → 摘花生 → 大盗阿福 → 最大子段和 → 最大子阵和 → 长度至少为 $k$ 的最大子段和。前四题先把状态和转移写准确，后两题再练习如何用前缀和把范围限制转化成更快的计算。