最大字段和（与a[i]有关
这个有点意思。
核心思路（Kadane 算法）：“边走边选”
想象你从第一个数开始，逐个往后走，每走到一个数，只做两个选择：
- 选：把当前数加入 “之前选的那段”，继续累加；
- 不选：扔掉之前选的所有数，从当前数重新开始。
如果原来的dp[i-1]加上当前的a[i]得到的结果，结果还没有当前的a[i]大，那就从当前的开始选（用来解决正负的问题）
- 每次选完后，记录一下 “当前能凑出的最大和”，最后全局最大的那个就是答案。
代码里的关键变量（对应思路）
a[i]：存储原始的数字数组；dp[i]：表示 “以第 i 个数结尾的连续子数组的最大和”（比如dp[3]就是以第 4 个数结尾的最大和）；max_sum：记录遍历过程中所有dp[i]的最大值（最终答案）
二、通俗解释代码的执行步骤
以测试用例 5 -2 1 -3 4 -1 为例（n=5，数组是[-2,1,-3,4,-1]），一步步看代码怎么跑：
步骤 1：初始化
- 读取 n=5，读取数组
a = [-2,1,-3,4,-1]；
dp[0] = a[0] = -2（第一个数结尾的子数组只能是它自己）；max_sum = -2（初始最大和就是第一个数）。
步骤 2：遍历第 2 个数（i=1，a [1]=1）
步骤 3：遍历第 3 个数（i=2，a [2]=-3）
步骤 4：遍历第 4 个数（i=3，a [3]=4）
步骤 5：遍历第 5 个数（i=4，a [4]=-1）
步骤 6：输出结果
最终max_sum=4，就是答案（对应子数组[4]）。
五、核心逻辑一句话总结
二选一（延续前序子数组 / 重新开始）
每走到一个数，就判断 “带着前面的数一起算” 和 “重新开始算” 哪个更划算，选划算的那个，同时记录过程中出现过的最大值，就是最终答案。
六、补充：代码为什么能跑快？
整个过程只遍历数组一次，时间是 O (n)（n 个数走 n 步），不管数组多长，都能很快算出结果，这也是 Kadane 算法的核心优势（比暴力枚举所有子数组的 O (n²) 快得多）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
using namespace std;
long long dp[10000001];
long long a[10000001];
long long maxx;
int main ()
{
int n;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>a[i];
}
dp[0]=a[0];
maxx=a[0];
for(int i=1;i<n;i++){
dp[i]=max(dp[i-1]+a[i],a[i]);
if(dp[i]>maxx){
maxx=dp[i];
}
}
cout<<maxx<<endl;
}
}
|
字符串区间翻转问题
原字符串 1 的个数+收益数组的最大子数组和
输入样例：4，1001
- 原字符串 1 的个数：
count_1 = 2（第 1 位和第 4 位是 1）。
- 收益数组（最大字段和）：
[-1, 1, 1, -1]。
- Kadane 算法求最大子数组和：子数组
[1,1]（对应原字符串第 2、3 位），收益为 2。
- 最终结果：
2 + 2 = 4，与样例输出一致。
最长递增子序列数量/求和、最长连续递增子序列、最长连续子串且求出这一串元素（与dp[i]有关
不连续递增⼦序列的跟前0-i 个状态有关，连续递增的⼦序列只跟前⼀个状态有关
一般都会问数量，但如果让你把具体是哪些数组成了这个最长子序列/最长子串，要使用start和end记录开始和结束的下表
dp含义：以dpi结尾的序列，最长的子序列是多少
递推式：dpi=max(dpj+1,dpi)；
初始化：dp0=1
遍历顺序：
1
2
3
4
5
| for(int i=0;i<n;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(dp[j]<dp[i]){
dp[i]=max(dp[j]+1,dp[i])
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
using namespace std;
int main ()
{
int nums[10]={0,1,0,3,2,3};
int dp[10];
dp[0]=1;
for(int i=0;i<6;i++){
//数量初始化
dp[i]=1;
//求和初始化
for(int i = 0; i < n; i++){
dp[i] = a[i];
}
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
//数量
dp[i]=max(dp[j]+1,dp[i]);
//求和
dp[i]=max(dp[j]+nums[i],dp[i]);
}
}
}
int result=dp[0];
for(int i=0;i<6;i++){
result=max(result,dp[i]);
}
cout<<result;
}
|
那么这一串元素要怎么求呢
对于开头，我们必须使用一个start数组，vector start(k+1);并初始化start[0] = 0;
最长公共子序列数量、最长公共子序列输出
一定注意数组初始化的问题，尤其是开数组的时候，要么用vector<int> dp(a+1,vector(b+1,0).要么直接开一个超大的静态数组，然后memset(dp,0,sizeof(dp))
1
2
3
4
| int dp[5][5] = {0}; // 合法！C++支持：第一个元素置0，其余元素默认初始化为0
int l1=3, l2=4;
int dp[l2+1][l1+1] = {0}; // 非法！C++标准不允许，且编译器扩展支持时也仅能初始化第一个元素，其余是随机垃圾值
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
using namespace std;
int main ()
{
string s1,s2;
//用空格隔开的话就直接cin，如果需要读入空格采用getline
while(cin>>s1>>s2){
int l1=s1.size(),l2=s2.size();
//这里使用l1+1是因为最外面还有一圈0，只开l1的话不够用
vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));
for(int i=1;i<=l1;i++){
for(int j=1;j<=l2;j++){
if(s1[i-1]==s2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
//这里不用加1
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
}
}
}
cout<<dp[l1][l2]<<endl;
}
}
|
最长子序列输出1730
这就是最长和连续最长的区别// 如果字符不匹配，当前连续长度重置为0
思路是记录下end_index，获得字符串长度m后，m-end__index既是开头，然后使用substr截取出来输出
这里有一点要注意，如果是输出最后一个的话，则比较的条件变成>=，这样即使是一样的也会取到最后一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
using namespace std;
int main ()
{
string s1,s2;
while(cin>>s1>>s2){
int l1=s1.size(),l2=s2.size();
vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));
int max_len =0;
int end_idx=-1;
for(int i=1;i<=l1;i++){
for(int j=1;j<=l2;j++){
if(s1[i-1]==s2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
if(dp[i][j]>=max_len){
max_len=dp[i][j];
end_idx=i;
}
}
// 如果字符不匹配，当前连续长度重置为0
else{
dp[i][j] = 0;
}
}
}
cout << max_len << endl;
if(max_len>0){
int start=end_idx-max_len;
string re=s1.substr(start,max_len);
cout<<re<<endl;
}
}
}
|
最长连续重复子数组
整数拆分
dp含义：乘积最大为多少
递推式：dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))
由于动态数组初始化全部为零，初始dp[i]=0，外层max判断是否要更新为最新值
max(j*(i-j),j*dp[i-j])，前者为不拆，后者为拆
初始化：dp0=0,dp1=0(题目给的范围里这两个没意义)，dp[2]=1
遍历顺序：
1
2
3
| for(int i=2;i<=n;i++){
for(int j=1;j<=i/2;j++){
递推式
|
简单01背包问题
即dp[i][j] 表示从下标为**[0-i]的物品⾥任意取，放进容量为j**的背
包，价值总和最⼤是多少。
- 确定dp数组以及下标的含义
对于背包问题，有⼀种写法， 是使⽤⼆维数组，即dp[i][j] 表示从下标为[0-i]的物品⾥任意取，放进容量为j的背
包，价值总和最⼤是多少。
只看这个⼆维数组的定义，⼤家⼀定会有点懵，看下⾯这个图：
要时刻记着这个dp数组的含义，下⾯的⼀些步骤都围绕这dp数组的含义进⾏的，如果哪⾥看懵了，就来回顾⼀下i
代表什么，j⼜代表什么。
- 确定递推公式
再回顾⼀下dp[i][j]的含义：从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少。
那么可以有两个⽅向推出来dp[i][j]，
不放物品i：由dp[i - 1][j]推出，即背包容量为j，⾥⾯不放物品i的最⼤价值，此时dp[i][j]就是dp[i - 1][j]。(其
实就是当物品i的重量⼤于背包j的重量时，物品i⽆法放进背包中，所以背包内的价值依然和前⾯相同。)
放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最
⼤价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最⼤价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[21][1010];
int w[21], c[21];
int main(){
int N,V;
cin>>N>>V;
for(int i=1;i<=N;++i){
cin>>w[i]>>c[i];
}
for(int j = c[1]; j <= V; j++){
dp[1][j] = w[1];
}
for(int i=2;i<=N;++i){
for(int j=0;j<=V;++j){
if(j>=c[i]){
dp[i][j] = max(dp[i-1][j-c[i]] + w[i], dp[i-1][j]);
}
else{
dp[i][j] = dp[i-1][j];
}
}
}
cout<<dp[N][V]<<endl;
return 0;
}
|
1086采药
此类题一定要让数组从1开始，不然会有很多麻烦
想一想数组第一行初始化的时候要让i等于多少？
遍历的时候ij的范围是多少？比较的时候j要不要加等于号？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
int main ()
{
int t,m;
while(cin>>t>>m){
vector<int> att(m+1);
vector<int> amm(m+1);
vector<vector<int>> dp(m + 1, vector<int>(t + 1, 0));
for(int i=1;i<=m;i++){
cin>>att[i]>>amm[i];
}
for(int i=att[1];i<=t;i++){
dp[1][i]=amm[1];
}
for(int i=2;i<=m;i++){
for(int j=0;j<=t;j++){
if(j>=att[i]){
dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i-1][j-att[i]]+amm[i]));
}
else
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[m][t]<<endl;
}
}
|
完全背包
与01背包的区别是不用初始化
而且如果选则加入的话，递推式变成 dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-att[i]]+amm[i]));原因是01背包选完i后只能从i-1开始选，而完全背包选完i后仍然可以选择i
初始化时，vector<vector>代表是开一个二维数组，里面的每个一维数组也是vector类型。有n+1行，每行是一个vector类型,长度为w+1，初始化为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <bits/stdc++.h>
using namespace std;
int main ()
{
int n,w;
while(cin>>n>>w){
vector<int> att(n+1);
vector<int> amm(n+1);
vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
for(int i=1;i<=n;i++){
cin>>att[i]>>amm[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=w;j++){
if(j>=att[i]){
dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-att[i]]+amm[i]));
}
else
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][w]<<endl;
}
}
|
字符串编辑距离
回溯算法
模版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果;
}
}
|
计算组合数（1234里面挑两个）(回溯，用了对数组push_back）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void backt(int n, int k, int s_idx) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = s_idx; i <= n; i++) {
path.push_back(i);
backt(n, k, i + 1);
path.pop_back();
}
}
int main() {
int n = 4, k = 2;
backt(n, k, 1);
cout << "所有" << k << "个数的组合：" << endl;
for (auto& vec : result) {
for (int num : vec) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
|
合并石子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<bits/stdc++.h>
using namespace std;
int a[1001],dp[1001][1001],sum[1001];
int main() {
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]+=sum[i-1]+a[i];
}
for(int len=2;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
dp[i][j]=1e8;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
}
cout<<dp[1][n];
}
|
字符串编辑距离
问题描述：给定两个字符串A和B，求字符串A至少经过多少步字符操作变成字符串B。
我们先以一个例子分析，比如eat变成tea。对于第一个字符，e != a，所以要想让这两个字符相等，有三种可以选择的办法
- 修改字符，将e直接变成a，需要走1步。
- 插入字符，在e的前面插入a，也需要走1步。
- 删除字符，将e删除，然后比较后面的与a，也需要走1步。
1
2
3
4
5
6
7
8
9
| 原理：
给出一个初始化矩阵，逐位比较两个字符串，待修改的矩阵对应为行，被比较的矩阵对应位列
若字符串对应的位相同，则让该矩阵位直接让这一位的矩阵的等于左上对角的值
否则，有三种情况，分别是：
①：等于上面矩阵位加一
②：等于左上角矩阵位加一
③：等于左边矩阵位加一
最后该矩阵位取上面三种情况中最小的一中。
最右下角的一位保存的就是字符串编辑距离
|
初始化如下所示：因为相当于把字符串全部删除所需要的步数
|
|
a |
b |
c |
d |
|
0 |
1 |
2 |
3 |
4 |
| a |
1 |
|
|
|
|
| c |
2 |
|
|
|
|
| d |
3 |
|
|
|
|
更新过程：
相等：抄左上角的
不相等：min(左边加一，上面加一，左上角加一)
|
|
a |
b |
c |
d |
|
0 |
1 |
2 |
3 |
4 |
| a |
1 |
0 |
1 |
2 |
|
| c |
2 |
1 |
1 |
1 |
|
| d |
3 |
2 |
2 |
2 |
|
微信
支付宝