PAT A1045 动态规划

该题目有两种解法，都是动态规划中特别经典的解法，一种是最长不下降子序列，一种是最长公共子序列；

第一种方法对于该题目其实有点取巧的感觉；

首先，注意一点，对于最长不下降子序列来说，其序列的元素一定是非递减的，所以我们的当务之急是如何将值转换为

递增序列，从而使得算法能够继续进行；

对于这个问题，我们可以使用hashtable进行处理，也就是利用hashtable重新使得值递增；

这里需要注意一下，子序列递增研究的是不连续的子序列，连续的子序列其实可以用前面的KMP算法来及进行解决；

对于该问题，首当其中的还是状态转移方程。由于该问题还是从0开始研究，所以仍然设置一个一维数组dp来储存中间的状态；

大致思路是限定一个子串序列，然后选择一个，从第一个开始进行轮询，这里有点像插入 排序 的感觉；

其状态转移方程为dp[i]=max(1,dp[j]+1);

该方程可以理解将第i个元素排在j后面，从而继承j之前的子串序列的长度，1为单个元素的序列长度；

代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxc=210;
const int maxn=10010;
int Hashtable[maxc];
int a[maxn],dp[maxn];
int main(){
    int n,m,x;
    scanf("%d%d",&n,&m);
    memset(Hashtable,-1,sizeof(Hashtable));
    for(int i=0;i<m;i++){
        scanf("%d",&x);
        Hashtablet[x]=i;
    }
    int L,num=0;
    scanf("%d",&L);
    for(int i=0;i<L;i++){
        scanf("%d",&x);
        if(Hashtable[x]>=0){
            a[num++]=Hashtable[x];
            //进行hashtable的相应转换
        }
    }
    int ans=-1;
    for(int i=0;i<num;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(a[j]<=a[i]&&dp[i]<dp[j]+1){
                dp[i]=dp[j]+1;
            }
        }
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

第二种不太好理解，所以这里先不再赘述，主要是不能理解为什么公共部分可以重复输出；