递推求解
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 网友:两个二维状态转移方程本来就不一样,利用滚动数组后状态一样了,完全是巧合