AKSZ-动态规划
2024-06-23 17:21:34
发布于:广东
动态规划
1.划分阶段:斐波那契数列的每一项作为一个阶段
2.确定状态:第项的值用数组第位表示:
3.确定转移方程:
结尾法:就表示以下标结尾的答案
1,最优化原理:最优解所包含的子问题的解也是最优的
2.无后效性:某状态以后的过程不会影响以后的决策
3.子问题重叠:子问题直接不独立
结尾法示例
最长上升子序列
#include<bits/stdc++.h>
using namespace std;
int n,a[1001],dp[1001],ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[i]>a[j])dp[i] = max(dp[i], dp[j] + 1);
}
}
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}
前缀法:表示~处理完毕的结果,就是答案
前缀法示例
最长公共子序列
#include<bits/stdc++.h>
using namespace std;
char x[1005],y[1005];
int dp[1005][1005];
int main(){
cin>>x+1>>y+1;
int l1=strlen(x+1),l2=strlen(y+1);
for(int i=1;i<=l1;i++){
for(int j=1;j<=l2;j++){
if(x[i]==y[j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[l1][l2];
return 0;
}
这里空空如也
有帮助,赞一个