递推求解
N级楼梯上楼问题：一次可以走一级或两级，问有多少种上楼方式 。
思路：首先设有n级台阶上有f(n)种方式；倒推，从最后一步开始想：因为在最上面一级可以退1步或2步，也就是说，f(n)可以由f(n-1)和f(n-2)相加得到，也就是到达n-2级的方式数 加上到达n-1级的方式数 。
so，状态转移方程get：f(n)=f(n-1)+f(n-2) 。其实也就是斐波那契数列啦！
【王道机试 DP篇】#includeusing namespace std;unsigned long long a[100]= {1,2};//注意这里要long longint main(){int n;while(cin>>n){for(int i=2; i
LIS
72bf72d63670611052521b1c226bfb15
刚开始看讲解感觉理解困难，写了代码仿佛秒懂了，但是怎么构建这么个dp【用来存以ai结尾的LIS的最长长度，最后在for一遍找到全局最长的LIS】，还需要深入思考+总结
case1：拦截导弹，这就是LIS的镜像版本LDS？就是每次往前找>=当前位置的即可
#include#includeusing namespace std;const int N=30;int a[N];int dp[N];//存每个以ai结果的最长递增子序列的元素数int main() {int n;while(cin>>n, n!=0) {memset(dp,0,sizeof(dp));for(int i=0; i=a[i]) {if(dp[j]+1>tmax)tmax=dp[j]+1;//这就是基于前面已经找到了的lIS，看能否在这基础上更“长”}}dp[i]=tmax;}int ans=-1;for(int i=0; ians)ans=dp[i];printf("%d\n", ans);}return 0;}
case2：合唱队形，问一个序列要满足先增后减序列，最少要去掉几个数
#includeusing namespace std;const int N=105;int a[N];int dp1[N],dp2[N];//正向上升，反向上升！int main() {//17:41->sint n,ma;while(scanf("%d",&n)!=EOF, n) {for(int i=0; ii; j--) {if(a[j]ma)ma=dp1[i]+dp2[i];}printf("%d\n", n-ma+1);}return 0;}
LCS
case1：裸的LCS，以下为标准版子，几个细节
#includeusing namespace std;const int N=105;string a,b;int dp[N][N];//dp[i][j]表示a和b在前i和j个字符时的LCS长度int main() {while(cin>>a>>b) {int la=a.length();int lb=b.length();for(int i=0; i<=la; i++) dp[i][0]=0; //共la+1个数要initfor(int j=0; j<=lb; j++) dp[0][j]=0;for(int i=1; i<=la; i++) {//1~lafor(int j=1; j<=lb; j++) {if(a[i-1]==b[j-1])//把i-1当做上次位置，每次递推当前的i位置dp[i][j]= dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i][j-1], dp[i-1][j]);}}printf("%d\n", dp[la][lb]);}return 0;}
背包
01背包：每个物品选1或不选 。二维的情况好理解多了，dp[i][j]为选到前i个物品时剩余容量j时的最大收益，就是从头开始填表 。注意
#includeusing namespace std;const int N=1005;int w[N];//重量int v[N];//收益int dp[N][N];//dpij表示体积<=j时，前i个物品达到的最大收益int W,n;//容量，物品数void show_dp() {for(int i=1; i<=n; i++) {for(int j=0; j<=W; j++)cout<>W>>n) {if(!W && !n) break;for(int i=1; i<=n; i++)//必须从1开始，因为0有“没选物品”的含义，不能缺少！cin>>w[i]>>v[i];for(int j=0; j<=W; j++) dp[0][j]=0;//没选的话，都是0 for(int i=1; i<=n; i++) {for(int j=w[i]; j<=W; j++)//够装 dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);for(int j=w[i]-1; j>=0; j--)//不够装 dp[i][j]=dp[i-1][j];//show_dp();}cout<
使用“滚动数组”压缩空间，下面这段话写的非常好，细细品味
完全背包，与01背包区别 仅在于每个物品可以选多次 。一维数组的情况，和01背包完全一样，只是变成了正序遍历j
#includeusing namespace std;const int N=1005;int w[N];//重量int v[N];//收益int dp[N];//体积<=j时，能达到的最大收益int W,n;//时间，物品数void show_dp() {for(int j=0; j<=W; j++)cout<>W>>n) {if(!W && !n) break;for(int i=1; i<=n; i++)//必须从1开始，因为0有“没选物品”的含义，不能缺少！cin>>w[i]>>v[i];for(int j=0; j<=W; j++) dp[j]=0; //也要都init=0 。理解为，虽把时间维度去了，//但是其实刚开始是要全部赋为0，表示了时间维度的意义，即“没选”时，收益都是0for(int i=1; i<=n; i++) {for(int j=w[i]; j<=W; j++)dp[j]=max(dp[j], dp[j-w[i]]+v[i]);show_dp();}cout<
而一维数组的正序倒序的区别在于，有多种理解方式：
《王道》另一种理解： from 网友：两个二维状态转移方程本来就不一样，利用滚动数组后状态一样了，完全是巧合