动态规划最后专题训练

1.蓝肽子序列

// 求第一个大写+后面字母小写的公共子序列
#include <bits/stdc++.h>
using namespace std;
string s1[1010],s2[1010]; //存取序列字符串
int dp[1010][1010]; //最长公共(蓝肽)子序列
int main()
{memset(dp,0,sizeof(dp));string ss1,ss2;cin>>ss1>>ss2;int a1=0,a2=0;for(int i=0; i<ss1.size(); i++){if(isupper(ss1[i])){a1++;}s1[a1]+=ss1[i]; //初始化，所求所有蓝肽子序列}for(int i=0; i<ss2.size(); i++){if(isupper(ss2[i])){a2++;}s2[a2]+=ss2[i];}for(int i=1; i<=a1; i++){for(int j=1; j<=a2; j++){if(s1[i]==s2[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[i][j]<<" ";}}cout<<dp[a1][a2]<<endl;return 0;
}

2. 爬楼梯

class Solution {
public:int climbStairs(int n) {if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) { // 注意i是从3开始的dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

3.使用最小花费爬楼梯

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0; // 默认第一步都是不花费体力的dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.size()];}
};

4.爬楼梯进阶

#include <iostream>
#include <vector>
using namespace std;
int main()
{//背包问题：有顺序遍历背包后遍历物品，完全背包物品顺序遍历 int n, m;while (cin >> n >> m){vector<int> dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; i++)   // 遍历背包{for (int j = 1; j <= m; j++)   // 遍历物品{if (i - j >= 0) dp[i] += dp[i - j];}}cout << dp[n] << endl;}
}

5.台阶方案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a,b,c,n;
const int N=1000000007;
ll dp[1000010]; //1-i方案数
int main()
{cin>>n>>a>>b>>c;memset(dp,0,sizeof(dp));dp[0]=1;for(int i=1; i<=n; i++){if(i-a>=0){dp[i]+=dp[i-a];}if(i-b>=0){dp[i]+=dp[i-b];}if(i-c>=0){dp[i]+=dp[i-c];}dp[i]%=N; //此处才开始求余，防止三种台阶方式是交叉情况}cout<<dp[n]<<endl;return 0;
}

6. 填充

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
int dp[1000010];
int main()
{cin>>s;for(int i=1; i<s.size(); i++){if(s[i]==s[i-1] || s[i-1]=='?' || s[i]=='?') //可以替换{//选择拼接和不拼接dp[i]=max(dp[i-2]+1,dp[i-1]);}else{dp[i]=dp[i-1]; }}cout<<dp[s.size()-1]<<endl;return 0;
}

7. 子2023

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
ll dp[4];
int main()
{for(int i=1; i<=2023; i++){s+=to_string(i);}for(int i=0; i<s.size(); i++){if(s[i]=='2'){dp[0]++; //以2结尾 dp[2]+=dp[1]; //以202结尾 }if(s[i]=='0'){dp[1]+=dp[0]; //以20结尾 }if(s[i]=='3'){dp[3]+=dp[2]; //以2023结尾 }}cout<<dp[3]<<endl;  return 0;
}