动态规划经典题型课堂笔记

一、回文子串计数（DP法）

思路分析

1. 问题痛点：若暴力判断每个子串是否为回文，需 $O(n^3)$ 时间（枚举所有子串 $O(n^2)$，每个子串遍历判断 $O(n)$）。
2. DP优化核心：利用子问题结果推导父问题——若子串 i+1 到 j-1 是回文，且两端字符 s[i] == s[j]，则 i 到 j 也是回文，避免重复遍历。
3. 状态定义：dp[i][j] 表示下标从 i 到 j 的子串是否为回文（1 是，0 否）。
4. 转移方程：若 dp[i+1][j-1] == 1 且 s[i] == s[j]，则 dp[i][j] = 1。
5. 边界条件：
   • 长度为 1：单个字符一定是回文，即 dp[i][i] = 1。
   • 长度为 2：两个相同字符是回文，即若 s[i] == s[i+1]，则 dp[i][i+1] = 1。
6. 枚举顺序：按子串长度从小到大枚举（len 从 3 到 n），保证计算长串时，其内部短串已算好。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,a[N],ans;
string s;
int dp[N][N];  // dp[i][j]: 下标i到j的子串是否为回文(1是/0否)

int main(){
    cin>>n>>s;
    s="@"+s+"@";  // 下标从1开始，避免边界判断（如i-1越界）
    
    // 1. 初始化边界：先处理长度为1和2的子串（它们是长串的基础）
    for(int i=1;i<=n;i++){
        dp[i][i]=1;  // 单个字符一定是回文
        ans+=dp[i][i];
        if(s[i]==s[i+1]) {  // 两个相同字符也是回文
            dp[i][i+1]=1;
            ans++;
        }
    }
    
    // 2. 按长度从小到大枚举子串（保证计算i,j时，内部i+1,j-1已算好）
    for(int len=3;len<=n;len++){
        for(int L=1;L+len-1<=n;L++){
            int R=L+len-1;
            // 状态转移：若内部子串是回文 且 两端字符相等，则当前子串也是回文
            if(dp[L+1][R-1]==1&&s[L]==s[R]) {
                dp[L][R]=1;
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

二、最大两段子段和

思路分析

1. 问题转化：要找两个不重叠的子段，使它们的和最大。可将数组从中间分割为前后两部分，分别求前半段的最大子段和与后半段的最大子段和，再相加。
2. 预处理前缀：
   • dp[i]：以第 i 个数结尾的最大子段和（要么重新开始，要么接在前面的子段后）。
   • ma[i]：前 i 个数的最大子段和（即 dp[1] 到 dp[i] 的最大值）。
3. 预处理后缀：
   • dp2[i]：以第 i 个数开头的最大子段和（要么重新开始，要么接在后面的子段前）。
   • ma2[i]：从第 i 个数到第 n 个数的最大子段和（即 dp2[i] 到 dp2[n] 的最大值）。
4. 枚举分割点：遍历所有可能的分割点 i（前半段 1~i，后半段 i+1~n），取 ma[i] + ma2[i+1] 的最大值。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int t,n,a[N],dp[N],dp2[N],ma[N],ma2[N];
// dp[i]: 以i结尾的最大子段和
// ma[i]: 前i个数的最大子段和（dp[1]~dp[i]的最大值）
// dp2[i]: 以i开头的最大子段和
// ma2[i]: 从i到n的最大子段和（dp2[i]~dp2[n]的最大值）

int main(){
    cin>>t;
    ma[0]=-1e9;  // 初始化为极小值，防止全负数情况出错
    while(t--){
        cin>>n;
        // 1. 预处理前缀：从左到右，计算以i结尾的最大子段和 及 前i个的最大值
        for(int i=1;i<=n;i++){
            cin>>a[i];
            dp[i]=max(a[i],a[i]+dp[i-1]);  // 两种选择：重新开始 或 接在前面的子段后
            ma[i]=max(ma[i-1],dp[i]);       // 前i个的最大值 = max(前i-1个的最大值, 以i结尾的最大值)
        }
        
        // 2. 预处理后缀：从右到左，计算以i开头的最大子段和 及 i到n的最大值
        dp2[n+1]=-1e9;
        ma2[n+1]=-1e9;
        for(int i=n;i>=1;i--){
            dp2[i]=max(a[i],a[i]+dp2[i+1]); // 两种选择：重新开始 或 接在后面的子段前
            ma2[i]=max(dp2[i],ma2[i+1]);     // i到n的最大值 = max(以i开头的最大值, i+1到n的最大值)
        }
        
        // 3. 枚举所有分割点，取前后两部分最大值之和的最大
        int ans=-1e9;
        for(int i=1;i<n;i++){
            ans=max(ans,ma[i]+ma2[i+1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

三、长度至少为k的最大子段和（前缀和优化）

思路分析

1. 前缀和转化：子段 L~R 的和 = 前缀和 s[R] - s[L-1]。
2. 约束处理：要求子段长度≥k，即对于固定右端点 R，左端点 L 需满足 L ≤ R - k + 1。
3. 优化目标：对于每个 R，要最大化 s[R] - s[L-1]，等价于最小化 s[L-1]（其中 L-1 ≤ R - k）。
4. 维护最小值：用 mi[i] 记录前 i 项前缀和的最小值，枚举 R 时直接取 mi[R - k] 即可快速得到最小的 s[L-1]。

代码实现

#include<bits/stdc++.h>
#define int long long  // 数据范围大，防止溢出
using namespace std;
const int N = 1e6 + 10;
int t, n, a[N], k, s[N], mi[N],ans=-1e18;
// s[i]: 前i项前缀和（s[0]=0, s[1]=a[1], s[2]=a[1]+a[2], ...）
// mi[i]: 前i项前缀和的最小值（mi[i] = min(s[0], s[1], ..., s[i])）

signed main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		s[i] = s[i - 1] + a[i];       // 计算前缀和
		mi[i] = min(mi[i - 1], s[i]); // 维护前i项前缀和的最小值
	}
	
	// 枚举右端点R，找长度≥k的最大子段和
	for (int R = k; R <= n; R++){
		int L = R - k + 1;  // 左端点最远到L，保证子段长度≥k
		// 子段和 = s[R] - s[L'-1]，要最大化则需最小化s[L'-1]（L'≤L → L'-1≤L-1=R-k）
		ans = max(ans, s[R] - mi[L - 1]);
	} 
	cout<<ans;
	return 0;
}

四、最长上升子序列（LIS）

思路分析

1. 状态定义：dp[i] 表示以第 i 个数结尾的最长上升子序列长度。
2. 转移方程：对于每个 i，枚举前面所有 j < i，若 a[j] < a[i]，则可将 a[i] 接在以 a[j] 结尾的子序列后，此时 dp[i] = max(dp[i], dp[j] + 1)。
3. 边界条件：每个数自身就是一个子序列，故 dp[i] = 1。
4. 结果提取：遍历所有 dp[i]，取最大值即为整个数组的最长上升子序列长度。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,a[1234],dp[1234]; 
// dp[i]: 以第i个数结尾的最长上升子序列长度

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=1;
	for(int i=1;i<=n;i++){
        dp[i]=1;  // 边界：至少可以选自己一个数，长度为1
		// 枚举前面所有比a[i]小的数，尝试把a[i]接在后面
		for(int j=1;j<i;j++){
			if(a[j]<a[i]){
				dp[i]=max(dp[j]+1,dp[i]); // 取最长的情况更新dp[i]
			}
		}
		ans=max(ans,dp[i]); // 更新全局最长上升子序列长度
	}
	cout<<ans;
	return 0;
}