例题1
组成平方数
题目描述
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
输入输出描述
输入描述
一个整数n,表示要组成的数字
输出描述
一个正数表示最少需要几个完全平方数才能组成
输入输出样例
输入格式#1：
4
输出格式#1：
1
输入格式#2：
10
输出格式#2：
2
输入格式#3：
19
输出格式#3：
3
输入格式#4：
245
输出格式#4：
2
输入格式#5：
3281
输出格式#5：
2
输入格式#6：
234
输出格式#6：
2
输入格式#7：
666
输出格式#7：
2
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int main()
{
int n;
cin>>n;
int dp[n+1];//从一开始
dp[0]=0;
for(int i=1;i<=n;i++)
{
dp[i]=i;
for(int j=1;i>=j*j;j++)
{
//见下图
dp[i]=min(dp[i],dp[i-j*j]+1);
}
}
cout<<dp[n];
}
例题2
删除一次得到子数组最大和
题目描述
给你一个整数
数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
输入输出描述
输入描述
一个整数数组arr
输出描述
最大和
输入输出样例
输入格式#1：
4
1 -2 0 3
输出格式#1：
4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
输入格式#2：
4
1 -2 -2 3
输出格式#2：
3
解释：我们直接选出 [3]，这就是最大和。
输入格式#3：
4
-1 -1 -1 -1
输出格式#3：
-1
最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
提示：
1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int main()
{
int len;
cin>>len;
int arr[len];
for(int i=0;i<len;i++)
{
cin>>arr[i];
}
//1 -2 0 3
int f[len];
int g[len];
f[0] = arr[0];
g[0] = -200001;
//-3 -4 -5 2
for(int i=1;i<len;i++)
{
//i=1 f[1]=max(-1,-2)=-1 g[1]=1
//i=2 f[2]=max(-1,0)=0 g[2]=1
//i=3 f[3]=max(3,3)=3 g[3]=4
f[i] = max(f[i-1]+arr[i],arr[i]);//其实就是f(i-1)是否<0
g[i] = max(g[i-1]+arr[i],f[i-1]);//取出g[i-1]加新数，和f[i-1]中最大值
}
int res = -2000000;
for(int i=0;i<len;i++){
res = max(res,max(f[i],g[i]));//取出f[i],g[i]最大值
}
cout<<res;
}
例题3
最大的连续子序列
题目描述
给定一个整形数组nums，找出一个序列中乘积最大的连续子序列该序列至少包含一个数。
输入输出描述
输入描述
共两行:
第一行，一个整形数据n，表示数据个数，
第二行有n个数据表示数据mum s。
输出描述
输出找到最大的连续子序列
输入输出样例
输入格式#1：
5
1 2 3 4 5
输出格式#1：
120
输入格式#2：
5
1 -2 3 -4 5
输出格式#2：
120
输入格式#3：
1
2
输出格式#3：
2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n],b[n],c[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int max1=b[0]=c[0]=a[0];
for(int i=1;i<n;i++)
{
//最大值乘以负数有可能变为最小值，最小值乘以负数有可能变为最大值
b[i]=max(max(a[i]*b[i-1],a[i]*c[i-1]),a[i]);//在不断的计算最大值
c[i]=min(min(a[i]*b[i-1],a[i]*c[i-1]),a[i]);//在不断的计算最小值
max1=max(max(b[i],c[i]),max1);
}
cout<<max1;
return 0;
}
例题4
普通背包
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int w[m],v[m],dp[n+1];
for(int i=0;i<m;i++)
{
cin>>w[i]>>v[i];
}
memset(dp, 0, sizeof(dp));
for(int i=0;i<m;i++)
{
for(int j=n;j>=0;j--)
{
if(j-w[i]>=0)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
cout<<dp[n];
}
感谢<mark>Albert.Jw</mark>发现错误
关键是内循环中为什么是逆序的呢，因为要记算当前状态的dp[j]，需要的是前一状态的dp[j]（即dp [j-1]），而逆序循环时前面的一定就是前一状态的dp[j]，可以直接拿来用，而正序循环之所以不可以，是因为当你计算完前面的dp[j]时，dp[j-1]存的就不是i-1时刻的值了，而你后面还要用dp[j-1]。当内循环是逆序时，就可以保证后一个dp[j]和dp[j-w[i]]+v[i]是前一状态的！
过程由于太多，请见下网址
https://dwz.cn/6hyKoSTA
例题5
完全背包
#include<cstdio>
#include<algorithm>
using namespace std;
int w[300],c[300],f[300010];
int V,n;
int main()
{
scanf("%d%d",&V,&n);
for(int i=1; i<=n; i++)
{
scanf("%d%d",&w[i],&c[i]);
}
for(int i=1; i<=n; i++)
{
for(int j=w[i]; j<=V; j++)//注意此处，与0-1背包不同，这里为顺序，0-1背包为逆序
{
f[j]=max(f[j],f[j-w[i]]+c[i]);
}
}
printf("max=%d\n",f[V]);
return 0;
}
过程由于太多，请见下网址
https://dwz.cn/GeY4UriQ
例题6
最大子段和
题目描述
给出一段序列，选出其中连续且非空的一段使得这段和最大。
输入输出描述
输入描述
第一行是一个正整数N，表示了序列的长度。
第二行包含N个绝对值不大于10000的整数Ai，描述了这段序列。
输出描述
一个整数，为最大的子段和是多少。子段的最小长度为1。
输入输出样例
输入格式#1：
7
2 -4 3 -1 2 -4 3
输出格式#1：
4
说明/提示
【样例说明】
2,-4,3,-1,2,-4,3中，最大的子段和为4，该子段为3,−1,2.
【数据规模与约定】
对于40%的数据，有N ≤ 2000
对于100%的数据，有N ≤ 200000
#include<bits/stdc++.h>
using namespace std;
int n[200001],p,ans[200001]={
0};//数组定义在外面
int main()
{
int sum=-9999999;//最小值
cin>>p;//个数
for(int i=1;i<=p;i++)
{
cin>>n[i];
ans[i]=max(ans[i-1]+n[i],n[i]);//等于前一个最大的字段加上这个数和这个数的最大值，不是顺着前一个，就是自己起一个头，看看那个的
sum=max(sum,ans[i]);//记录最大的
}
cout<<sum;//输出
return 0;
}
例题7
最长公共子序列
题目描述
给出1-n的两个排列P1和P2，求它们的最长公共子序列。
输入输出描述
输入描述
第一行是一个数n，
接下来两行，每行为n个数，为自然数1-n的一个排列。
输出描述
一个数，即最长公共子序列的长度
输入输出样例
输入格式#1：
5
3 2 1 4 5
1 2 3 4 5
输出格式#1：
3
说明/提示
【数据规模】
对于50%的数据，n≤1000
对于100%的数据，n≤100000
别的方法就不进行赘述了。
首先根据两个字符串的长度m，n生成一个（m + 1）x （n + 1）的数组dp，并且令dp[m][0] = 0，dp[0][n] = 0。为什么这么做呢，这里来解释一下：
动态规划是以空间换时间的利器吧，有了上个状态，经过我们的状态转移方程就可以推的下一阶段的状态。在这儿，每次操作的状态其实就是dp[i][j]的值。
2. 就这样，我手动的全部填完了。
然后呢，我们分析一下有没有什么规律？如上图所示，我们已知结果为abcf，怎么得到的呢？或者说能不能用某个规律来说明我是怎么填好每个空的？（当然我们的大脑比较厉害，反正会填，不会的估计题都没看明白或者出题的真的是非人类了）。
结论：当两个子串逐字符进行比较的时候，若发现了相同的字符，则此刻的dp[i][j] = dp[i - 1][j - 1] + 1。除此之外，dp[i][j]就看它上面的值和左边的值哪个大了，把大的值赋给它。
注意！我们虽然写的是dp[i][j]，但实际比较的是String1[i-1]和String2[j-1]。为啥呢？看图吧，当我填dp[i][j] = 1的时候，是因为我发现了String1[0] = String2[0] = "a"的时候吧？而此时的dp[i][j]中的i和j都等于1。现在多少明白为什么定义（m + 1）x（n + 1）了吧？为什么预先设定了哪些0？可以理解为两个字符串，其中一个若为空字符串，还有个锤子的公共子序列啊~
3.如上图所示，我们知道dp[i][j] 如何确定了吧！
#include <string>
#include <algorithm>
#include<iostream>
using namespace std;
string s1, s2;
int main()
{
cin >> s1;
cin >> s2;
int m = s1.size();
int n = s2.size();
int dp[n+1][m+1];
for(int i = 0; i < n+1; i++)
{
dp[i][0] = 0;
}
for(int i = 0; i < m+1; i++)
{
dp[0][i] = 0;
}
// 根据设定的规则一次填入dp[i][j]，其中i, j >= 1
for(int i = 1; i < n+1; i++)
{
for(int j = 1; j < m+1; j++)
{
if(s1[j-1] == s2[i-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else if(dp[i][j-1] > dp[i-1][j])
{
dp[i][j] = dp[i][j-1];
}
else
{
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[n][m] << endl;
return 0;
}
例题8
最长上升子序列
题目描述：
给定一个长度为 N 的数列，求它数值单调递增的子序列长度最大为多少。即已知有数列 A ， A=A1,A2…An ，求 A的任意子序列
B （ B=Ak1,Ak2…Akp ），使 B 满足 k1<k2<…<kp且 Ak1<Ak2<…<Akp 。现求 p
的最大值。
输入格式
共二行。
第一行是一个整数N
第二行有n个整数
输出格式
一个整数，最长上升子序列长度
输入输出样例
输入
8
186 186 150 200 160 130 197 220
输出
4
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int n,a[105],dp[105],ans;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<n;j++)
{
if(a[i]>a[j])
{
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int maxx=0;
for(int i=0;i<n;i++)
{
maxx=max(maxx,dp[i]);
}
cout<<maxx;
return 0;
}
京公网安备 11010502036488号