上目录：
目录
题目描述
输入格式
输出格式
输入输出样例
说明/提示
一、DP的意义以及线性动规简介
在一个困难的嵌套决策链中，决策出最优解。
二、动态规划性质浅谈
三、子序列问题
（一）一个序列中的最长上升子序列（LIS）
1、n^2做法
下一状态最优值=最优比较函数（已经记录的最优值，可以由先前状态得出的最优值）
2、n^log(n) 做法
（二）两个序列中的最长公共子序列（LCS）
dp[i][j]=max(dp[i][j],dp[i−1][j−1]+1);
dp[i][j]=max(dp[i−1][j],dp[i][j−1]
你可能很奇怪，为神马六级第一关是下楼梯？其实你去考场就要下楼梯，呵呵。
不说了，先看看考点：
我们要好好下楼梯，不要学小杨同学这样下楼梯：
题目描述
小杨发现，下楼梯时每步可以走 1 个台阶、2 个台阶或 3 个台阶。现在一共有 N 个台阶，你能帮小杨算算有多少种下楼梯方案吗？
输入格式
输入一行，包含一个整数 N。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
4
输出 #1
7
输入 #2
10
输出 #2
274
说明/提示
对全部的测试点，保证 1≤N≤60。
周知众所，连下两个或三个台阶会让小杨滚下楼梯，他不会那么做，故输出1即可。
题目是题目，现实是现实，你不要抢戏！
动态规划发自内心的一句话。
上面是有名的一个人——骗分神说的话，大家别当真。
一、DP的意义以及线性动规简介
动态规划自古以来是DALAO凌虐萌新的分水岭，但有些OIer认为并没有这么重要——会打暴力，大不了记忆化。但是其实，动态规划学得好不好，可以彰显出一个OIer的基本素养——能否富有逻辑地思考一些问题，以及更重要的——能否将数学、算筹学（决策学）、数据结构合并成一个整体并且将其合理运用。
而我们首先要了解的，便是综合难度在所有动规题里最为简单的了。线性动规既是一切动规的基础，同时也可以广泛解决生活中的各项问题——比如我们需要决策在相同的时间内做价值尽量大的事情，该如何决策，最优解是什么——这就引出了动态规划的真正含义：
在一个困难的嵌套决策链中，决策出最优解。
二、动态规划性质浅谈
首先，动态规划和递推有些相似（尤其是线性动规），但是不同于递推的是：
递推求出的是数据，所以只是针对数据进行操作；而动态规划求出的是最优状态，所以必然也是针对状态的操作，而状态自然可以出现在最优解中，也可以不出现——这便是决策的特性。
其次，由于每个状态均可以由之前的状态演变形成，所以动态规划有可推导性，但同时，动态规划也有无后效性，即每个当前状态会且仅会决策出下一状态，而不直接对未来的所有状态负责，可以理解为未来与过去无关。
三、子序列问题
（一）一个序列中的最长上升子序列（LIS）
例：由6个数，分别是： 1 7 6 2 3 4，求最长上升子序列。
评析：首先，我们要理解什么叫做最长上升子序列：1、最长上升子序列的元素不一定相邻 2、最长上升子序列一定是原序列的子集。所以这个例子中的LIS就是：1 2 3 4，共4个
1、n^2做法
首先我们要知道，对于每一个元素来说，最长上升子序列就是其本身。那我们便可以维护一个dp数组，使得dp[i]表示以第i元素为结尾的最长上升子序列长度，那么对于每一个dp[i]而言，初始值即为1.
那么dp数组怎么求呢？我们可以对于每一个i，枚举在i之前的每一个元素j，然后对于每一个dp[j],如果元素i大于元素j，那么就可以考虑继承，而最优解的得出则是依靠对于每一个继承而来的dp值，取max.
for(int i=1;i<=n;i++){dp[i]=1;//初始化 for(int j=1;j<i;j++)//枚举i之前的每一个j if(data[j]<data[i] && dp[i]<dp[j]+1)//用if判断是否可以拼凑成上升子序列，//并且判断当前状态是否优于之前枚举//过的所有状态,如果是，则↓ dp[i]=dp[j]+1;//更新最优状态 }
最后，因为我们对于dp数组的定义是到i为止的最长上升子序列长度，所以我们最后对于整个序列，只需要输出dp[n](n为元素个数)即可。
从这个题我们也不难看出，状态转移方程可以如此定义：
下一状态最优值=最优比较函数（已经记录的最优值，可以由先前状态得出的最优值）
2、n^log(n) 做法
我们其实不难看出，对于n^2做法而言，其实就是暴力枚举：将每个状态都分别比较一遍。但其实有些没有必要的状态的枚举，导致浪费许多时间，当元素个数到了100004−100005以上时，就已经超时了。而此时，我们可以通过另一种动态规划的方式来降低时间复杂度：
将原来的dp数组的存储由数值换成该序列中，上升子序列长度为i的上升子序列，的最小末尾数值。
这其实就是一种几近贪心的思想：我们当前的上升子序列长度如果已经确定，那么如果这种长度的子序列的结尾元素越小，后面的元素就可以更方便地加入到这条我们臆测的、可作为结果、的上升子序列中。
一定要好好看注释啊！
3、路径
只要记录前驱，然后递归输出即可（也可以用栈）
下面贴出完整代码
#include <iostream>
using namespace std;
const int MAXN = 1000 + 10;
int n, data[MAXN];
int dp[MAXN];
int from[MAXN];
void output(int x)
{if(!x)return;output(from[x]);cout<<data[x]<<" ";//迭代输出
}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>data[i];// DPfor(int i=1;i<=n;i++){dp[i]=1;from[i]=0;for(int j=1;j<i;j++)if(data[j]<data[i] && dp[i]<dp[j]+1){dp[i]=dp[j]+1;from[i]=j;//逐个记录前驱 }}int ans=dp[1], pos=1;for(int i=1;i<=n;i++)if(ans<dp[i]){ans=dp[i];pos=i;//由于需要递归输出//所以要记录最长上升子序列的最后一//个元素，来不断回溯出路径来 }cout<<ans<<endl;output(pos);return 0;
}
（二）两个序列中的最长公共子序列（LCS）
1、譬如给定2个序列：
1 2 3 4 53 2 1 4 5
试求出最长的公共子序列。
显然长度是3，包含3 4 5 三个元素（不唯一）
解析：我们可以用dp[i][j]来表示第一个串的前i位，第二个串的前j位的LCS的长度，那么我们是很容易想到状态转移方程的：
如果当前的A1[i]和A2[j]相同（即是有新的公共元素） 那么
dp[i][j]=max(dp[i][j],dp[i−1][j−1]+1);
如果不相同，即无法更新公共元素，考虑继承：
dp[i][j]=max(dp[i−1][j],dp[i][j−1]
那么代码:
#include<iostream>
using namespace std;
int dp[1001][1001],a1[2001],a2[2001],n,m;
int main()
{//dp[i][j]表示两个串从头开始，直到第一个串的第i位 //和第二个串的第j位最多有多少个公共子元素 cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&a1[i]);for(int i=1;i<=m;i++)scanf("%d",&a2[i]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1]);if(a1[i]==a2[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);//因为更新，所以++； }cout<<dp[n][m];
}
2、而对于洛谷P1439而言，不仅是卡上面的朴素算法，也考察到了全排列的性质：
对于这个题而言，朴素算法是n^2的，会被10^5卡死，所以我们可以考虑nlogn的做法：
因为两个序列都是1 n的全排列，那么两个序列元素互异且相同，也就是说只是位置不同罢了，那么我们通过一个map数组将A序列的数字在B序列中的位置表示出来——
因为最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后，可以考虑纳入LCS——那么就可以转变成nlogn求用来记录新的位置的map数组中的**LIS**。
最后贴n^log(n)代码：
#include<iostream>
#include<cstdio>
using namespace std;
int a[100001],b[100001],map[100001],f[100001];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);map[a[i]]=i;}for(int i=1;i<=n;i++){scanf("%d",&b[i]);f[i]=0x7fffffff;}int len=0;f[0]=0;for(int i=1;i<=n;i++){int l=0,r=len,mid;if(map[b[i]]>f[len])f[++len]=map[b[i]];else {while(l<r){ mid=(l+r)/2;if(f[mid]>map[b[i]])r=mid;else l=mid+1; }f[l]=min(map[b[i]],f[l]);}}cout<<len;return 0
}那么，这个题怎么解？
显然，设dp[i]为下到第i级台阶时的走法数，则有dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
dp[0]=1;不走也是一种走法
dp[1]=1;
dp[2]=2;
dp[3]=4;
好啦，你过了六级的第一关！不过是不是有跳关通道？我不知道啊。
)
)
