每日一题||动态规划练习
思路分析：
程序代码：
#include<iostream>using namespace std;char a[1005];//a串的前i个char b[1005];//b串的前j个int f[1005][1005];//表示前i个和前j个最长公共子序列int main(){scanf("%s",a+1);scanf("%s",b+1);int n=strlen(a+1);int m=strlen(b+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//状态转移方式1if(a[i]==b[j]){f[i][j]=max(f[i][j],f[i-1][j-1]+1);}//状态转移方式2和3f[i][j]=max(f[i][j],f[i-1][j]);f[i][j]=max(f[i][j],f[i][j-1]);}}printf("%d",f[n][m]);return 0;}
程序代码：
using namespace std;char a[1005];//a串的前i个char b[1005];//b串的前j个int f[1005][1005];//表示前i个和前j个最长公共子序列int main(){while(scanf("%s %s",a+1,b+1)==2){memset(f,0,sizeof(f));int n=strlen(a+1);int m=strlen(b+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//状态转移方式1if(a[i]==b[j]){f[i][j]=max(f[i][j],f[i-1][j-1]+1);}//状态转移方式2和3f[i][j]=max(f[i][j],f[i-1][j]);f[i][j]=max(f[i][j],f[i][j-1]);}}printf("%d\n",f[n][m]);}return 0;}
思路分析：
思路一：先求最长公共子序列，再求最长上升子序列（不可取）
a:7 1 5 6 4 2 7b:7 1 5 4 6 7 2最长公共子序列：7 1 5 6 2最长公共上升子序列：1 5 6实际上最长公共上升子序列：1 5 6 7
思路二：
定义字符串a，定义字符串b，定义表示最长公共上升子序列f[i][j]
状态表示：f[i][ j]表示a串前i个字符和b串前j个字符且以b[j]为结尾的最长公共上升子序列
状态计算：根据是否包含a[i]划分成两个集合
第一种情况：a[i]不纳入LCIS的情况，a[i]!=a[j]，也就是说a[i]和a[j]不配对
相当于求a的前i - 1个字符与b的前j个字符且以b[j]结尾的LCIS
动态转移方程：f[i][j]=f[i-1][j]
第二种情况：a[i]纳入LCIS的情况，a[i]==a[j]，也就是说a[i]和a[j]配对
相当于求a串前i - 1个字符和b的前j - 1个字符中找到一个最长的序列，这个序列以第k个结尾且b[k] < b[j]，也就是说k>=1&&k<j&&b[k]<b[j]，不能等于因为严格上升
包含a[i]这个子集继续划分，依据是子序列的倒数第二个数在b[]中是哪个数：
①：子序列只包含b[j]一个数，长度是1；
②：子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1；
③：…
④：子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；
动态转移方程：f[i, j] = max(f[i][j]，f[i - 1][k]+1)
程序代码：TLE代码
using namespace std;int a[3005];int b[3005];int f[3005][3005];int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){scanf("%d",&b[i]);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){//第一种情况：不纳入f[i][j]=f[i-1][j];//第二种情况：纳入if(a[i]==b[j]){f[i][j]=1;//初始化for(int k=1;k<j;k++){if(b[k]<b[j]){//保证最长上升f[i][j]=max(f[i][j],f[i][k]+1);}}}}}int maxx=0;for(int i=1;i<=n;i++){maxx=max(f[n][i],maxx);}printf("%d",maxx);return 0;}
程序代码：三层循环代码替换
for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= n; j ++ ){f[i][j] = f[i - 1][j];if (a[i] == b[j]){int maxv = 1;//替换1//for循环这部分主要优化替换3部分，也就是说如果出现了可以优化的情况for (int k = 1; k < j; k ++ )if (a[i] > b[k])//替换2 当a[i]>b[k]时才更新maxvmaxv = max(maxv, f[i - 1][k] + 1);f[i][j] = max(f[i][j], maxv);//替换3}}}
程序代码：O(n^3)---->O(n^2)
发现每次循环求得的maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值
using namespace std;int a[3005];int b[3005];int f[3005][3005];int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){scanf("%d",&b[i]);}for(int i=1;i<=n;i++){int maxv=1;for(int j=1;j<=n;j++){//第一种情况：不纳入f[i][j]=f[i-1][j];//第二种情况：纳入if(a[i]>b[j]) maxv=max(f[i][j]+1,maxv);if(a[i]==b[j]) f[i][j]=max(maxv,f[i][j]);}}int maxx=0;for(int i=1;i<=n;i++){maxx=max(f[n][i],maxx);}printf("%d",maxx);return 0;}