生活随笔
收集整理的這篇文章主要介紹了
DP经典5题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
DP一年多沒碰過了，今天突然想找找感覺，找了經典的幾道DP復習著敲了敲。雖然最大子矩陣，滑雪，石子合并等問題也足夠經典，我還是從中找了5道最經典的DP寫了這篇博文，如果您是大一，大二想踏入程序競賽的同學可以當習題做做，如果您像我一樣不是ACMer，平時項目中也很少用DP，同樣可以回顧一下DP的奧妙。
1.最大連續子序列之和
給定K個整數的序列{ N1, N2, ..., NK }，其任意連續子序列可表示為{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大連續子序列是所有連續子序中元素和最大的一個， 例如給定序列{ -2, 11, -4, 13, -5, -2 }，其最大連續子序列為{ 11, -4, 13 }，最大和為20。
狀態轉移方程：?sum[i]=max(sum[i-1]+a[i],a[i])
代碼清單：
[cpp]?view plaincopy
#include?"stdio.h"?? ?? main(){?? ????int?i,sum?=?0,?max?=?0;?? ????int?data[]?=?{?? ????????1,-2,3,-1,7?? ????};?? ????for(i?=?0;?i?<?sizeof(data)/sizeof(data[0]);?i++){?? ????????sum?+=?data[i];?? ????????if(sum?>?max)?? ????????????max?=?sum;?? ????????if(sum?<?0)?? ????????????sum?=?0;?????????? ????}?? ????printf("%d",max);?? }??
2.數塔問題
數塔問題 ：要求從頂層走到底層，若每一步只能走到相鄰的結點，則經過的結點的數字之和最大是多少？
轉移方程：sum[i] = max(a[左孩子] , a[右孩子]) + a[i]
[cpp]?view plaincopy
#include?"stdio.h"?? #define?N?5?? main(){?? ????int?i,j;?? ????int?data[N][N]?=?{?? ????????????{9,0,0,0,0},?? ????????????{12,15,0,0,0},?? ????????????{10,6,8,0,0},?? ????????????{2,18,9,5,0},?? ????????????{19,7,10,4,16}?? ????????};?? ????????for(i?=?N-1;?i?>?0;?i--)?? ????????????for(j?=?0;?j?<?i;?j++)?? ????????????????data[i-1][j]?+=?data[i][j]?>?data[i][j+1]???data[i][j]?:?data[i][j+1];?? ?????????? ????????printf("%d",data[0][0]);?? ?????????? ?????????? }??
3.01背包問題
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
轉移方程：dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]
[cpp]?view plaincopy
#include?"stdio.h"?? #define?max(a,b)?((a)>(b)?(a):(b))?? ?? ?? ?? main(){?? ?????? ????int?v?=?10?;???? ????int?n?=?5?;?????? ??????? ????int?value[]?=?{0,?8?,?10?,?4?,?5?,?5};??????? ????int?weight[]?=?{0,?6?,?4?,?2?,?4?,?3};????? ????int?i,j;?????? ????int?dp[n+1][v+1];?? ????for(i?=?0;?i?<?n+1;?i++)?? ????????for(j?=?0;?j?<?v+1;?j++)?? ????????????dp[i][j]?=?0;?? ?? ?? ????for(i?=?1;?i?<=?n;?i++){?? ????????for(j?=?1;?j?<=?v;?j++){?? ????????????if(j?>=?weight[i])?? ????????????????dp[i][j]?=?max(dp[i-1][j],dp[i-1][j-weight[i]]?+?value[i]);?? ????????????else?? ????????????????dp[i][j]?=?dp[i-1][j];?? ????????}?? ????}?? ?? ????printf("%d",dp[n][v]);?? }??
4.最長遞增子序列(LIS)
給定一個序列?An?=?a1?,a2?,? ... , an?，找出最長的子序列使得對所有?i?<?j?，ai?<?aj?。
轉移方程：b[k]=max(max(b[j]|a[j]<a[k],j<k)+1,1);
代碼清單：
[cpp]?view plaincopy
#include?"stdio.h"?? ?? main(){?? ????int?i,j,length,max=0;?? ????int?a[]?=?{?? ????????1,-1,2,-3,4,-5,6,-7?? ????};?? ????int?*b;?? ????b?=?(int?*)malloc(sizeof(a));?? ????length?=?sizeof(a)/sizeof(a[0]);?? ?? ????for(i?=?0;?i?<?length;?i++){?? ????????b[i]?=?1;?? ????????for(j?=?0;?j?<?i;?j++){?? ????????????if(a[i]?>?a[j]?&&?b[i]?<=?b[j]){?? ????????????????b[i]?=?b[j]?+?1;?? ????????????}?? ????????}?? ????}?? ????for(i?=?0;?i?<?length;?i++)?? ????????if(b[i]?>?max)?? ????????????max?=?b[i];?? ?????????? ????printf("%d",max);?? }??
5.最長公共子序列(LCS)
一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。
轉移方程：
dp[i,j] = 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?i=0 || j=0
dp[i,j] =?dp[i-1][j-1]+1 ? ? ? ? ? ? ? ? ? ? ? ?i>0,j>0, a[i] = b[j] ? ? ??
dp[i,j] = max(dp[i-1][j],dp[i][j-1]) ? ? ? ?i>0,j>0, a[i] != b[j]
[cpp]?view plaincopy
#include?"stdio.h"?? #define?M?8?? #define?N?6?? ?? ?????????? void?printLSC(int?i,?int?j,char?*a,?int?status[][N]){?? ????if(i?==?0?||?j==?0)?? ????????return;?? ????if(status[i][j]?==?0){?? ????????printLSC(i-1,j-1,a,status);?? ????????printf("%c",a[i]);?? ????}else{?? ????????if(status[i][j]?==?1)?? ????????????printLSC(i-1,j,a,status);?? ????????else?? ????????????printLSC(i,j-1,a,status);?? ????}?? }?? main(){?? ????int?i,j;?? ?? ????char?a[]?=?{'?','A','B','C','B','D','A','B'};?? ????char?b[]?=?{'?','B','D','C','B','A'};?? ????int?status[M][N];??? ????int?dp[M][N];?? ?? ????for(i?=?0;?i?<?M;?i++)?? ????????for(j?=?0;?j?<?N;?j++){?? ????????????dp[i][j]?=?0;?? ????????????status[i][j]?=?0;?? ????????}?? ?????????????? ????for(i?=?1;?i?<?M;?i++)?? ????????for(j?=?1;?j?<?N;?j++){?? ????????????if(a[i]?==?b[j]){?? ????????????????dp[i][j]?=?dp[i-1][j-1]?+?1;?? ????????????????status[i][j]?=?0;?? ????????????}?? ????????????else?if(dp[i][j-1]?>=?dp[i-1][j]){?? ????????????????dp[i][j]?=?dp[i][j-1];?? ????????????????status[i][j]?=?2;?? ????????????}?? ????????????else{?? ????????????????dp[i][j]?=?dp[i-1][j];?? ????????????????status[i][j]?=?1;?? ????????????}?? ?????????????????? ?????????????????? ????????}?? ????printf("最大長度：%d",dp[M-1][N-1]);?? ????printf("\n");?? ????printLSC(M-1,N-1,a,status);?? ????printf("\n");?? ?? }??
==================================================================================================
? 作者：nash_ ?歡迎轉載，與人分享是進步的源泉！
? 轉載請保留原文地址：http://blog.csdn.net/nash_/article/details/8247015
===================================================================================================
總結
以上是生活随笔為你收集整理的DP经典5题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
