最长上升子序列LCS

输入n及一个长度为n的数列，求出此序列的最长上升子序列长度。上升子序列指的是对于任意的i
    
     
      <=n<=1000,0<=ai<=1000000）
     
    

样例输入：

5

4 2 3 1 5

样例输出：

3（最长上升子序列为2, 3, 5）

#include
    
     #include
     
      const int N =1005;using namespace std;int shu[N];int DP[N]; int main(){    int m,n;    cin>>n;    for(int i=1;i<=n;i++){        cin>>shu[i];        DP[i]=1;//初始化DP距离数组     }    int t=0;    for(int i=1;i<=n;i++)      {         for(int j=1;j
     
    

题解：动态规划思想，定义一个数组dp[i]对应输入的数组，dp默认值为1（若数组是从大到小排列的 t为1），判断方法若shu[j]<shu[i]则为上升子序列的一部分所以dp[j]+1与dp[i]比较，找最大值，修改dp[i],结果最后遍历找最大值，当然边查边找最大值也行。

关于dp[j]+1和dp[i]的状态转换方程，有样例入手，如果出现dp[j]<dp[i]，那么dp[i]上不一定会变点的，若dp[i]>dp[j]那么肯定有dp[j]上的最大数量加上dp[i]条件必然也是满足的

所以说dp[j]+1要和dp[i]进行比较选择最大的作为dp[i]的最大上升子序列数量

最长公共子序列LCS

给定两个字符串s1和s2（长度均不超过1000），求出这两个字符串的最长公共子序列的长度。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         const int N=10010;char s1[N],s2[N];int dp[N][N];  //串s1的前i个字符 和 串s2的前j个字符的最长公共子序列长度using namespace std;int main(){    int m,n;    int len1,len2;    while(scanf("%s",s1)!=EOF){                scanf("%s",s2);         len1=strlen(s1);         len2=strlen(s2);         dp[0][0]=0;    //s1,s2都为空时         for(int i=1;i<=len1;i++)dp[i][0]=0;    //s2为空时   输出长度为0         for(int i=1;i<=len2;i++)dp[0][i]=0;     //s1为空时  输出长度为0                 for(int i=0;i
        
       
      
     
    

注释：设一个二维的数组，dp[i][j]模拟s1....si，s2......sj的最长公共子序列，动态规划的方法解决问题当前状态和下一状态，生成装填转换函数，

dp[i+1][j+1]=dp[i][j]+1, ①//若出现相等

max(dp[i][j+1], dp[i+1][j]), ②//否则

有点小乱等我在思考思考

最大公共子串LCS

给定两个字符串s1和s2（长度均不超过1000），求出这两个字符串的最大公共子串的长度。

这个比上一个简单一些吧第二步的状态转换函数改为0 就行

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxlen=1010;char s1[maxlen],s2[maxlen];int dp[maxlen][maxlen];    //dp[i][j]为串s1的前i个字符和串s2的前j个字符的最大公共子串长度int main(){    int i,j;    int len1,len2,ret;     //ret记录结果    while(scanf("%s",s1)!=EOF)    {        scanf("%s",s2);        memset(dp,0,sizeof(dp));   //初始化：开始LCS长度均为0        len1=strlen(s1);        len2=strlen(s2);        ret=0;        for(i=0;i