關於DP動規
今天學了動規，簡單記錄一下自己理解了的：（要不俺就忘了）
首先，啥是DP？？？
動態規劃，其實就是組合子問題的解來解決整個問題的解，由於每個子問題他只判斷一次，所以不會重複計算，那就很牛啊！！！
專業術語（複製加粘貼）：
1、 階段：把所給求解問題的過程恰當地分成若干個相互聯繫的階段，以便於按一 定的次序去求解，過程不同，階段數就可能不同．描述階段的變數稱為階段變數。
2、狀態：某一階段的出發位置成為狀態，通常一個階段有多個狀態。狀態通常可以用一個或一組數來描述，稱為狀態變數。
3、決策：一個階段的狀態給定以後，從該狀態演變到下一階段某個狀態的一種選 擇（行動）稱為決策。描述決策變數稱決策變數
4、策略和最優策略：所有階段的決策有序組合構成一個策略。 最優效果的策略叫最優策略。
5. 狀態轉移方程：前一階段的終點就是後一階段的起點，對前一階段的狀態作出某種決策， 產生後一階段的狀態，這種關係描述了由k階段到k+1階段狀態的演變規律，稱 為狀態轉移方程。
其實也沒什麼好說的，直接上題吧！
T1：從n個數中取出k個數，使得他們的和最大
解一：sort排序
這就沒啥可講的了，你就建一個cmp讓sort從大到小排序，選出前n大的數相加，就好啦，上程式碼！
//和最大問題（sort） #include<iostream> #include<algorithm> using namespace std; int a[1000000];//我不知道數據 int sum; int cmp(int x,int y) { return x>y; } int main() { int n,k;//n是總個數，k是取出的數的個數 cin>>n>>k; for(int i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n,cmp); for(int i=0;i<k;i++) { sum+=a[i]; } cout<<sum; return 0; }
解二：DP
用動規來解決，首先要想出狀態轉移方程（好像有點難很難）
我們首先定義一個二維數組f[i][j]，前面的表示第幾個數（i），後面表示已經選取了幾個數（j）
那麼我們分將其成兩種情況：我選或不選當前的數，
當我選取當前數時，它們的和就是上次的結果加上這個數，上次的結果就是f[i-1][j-1]（因為目前的數是i，所以上一個的考慮到的數就是i-1，又因我考慮了這個數，所以上個數就是j-1），當前的數是a[i]。那我們如果加上這個數，那麼現在所選數之和就是 f[i-1][j-1]+a[i]
那麼如果不選前面的數時，所得和其實就是選取上一個數時的和，即 f[i-1][j]，
所以我們就可以得出其狀態轉移方程：f[i][j]=max（ f[i-1][j-1]+a[i]，f[i-1][j]）
其他就好說了，具體如下
1 #include<iostream> 2 #define lxl long long 4 #define db double 5 using namespace std; 6 int f[10005][10005]; 8 int a[N]; 9 int n,k; 11 int main(){ 12 cin>>n>>k; 13 for(int i=1;i<=n;i++) 14 cin>>a[i]; 15 for(int i=1;i<=n;i++){ 16 for(int j=1;j<=k;j++){ 17 f[i][j]=max(f[i-1][j-1]+a[i],f[i-1][j]); 18 } 19 } 20 cout<<f[n][k]; 21 return 0; 22 }
T2.關於線性DP
從n個數中找出最長上升子序列（可以不連續），輸出其長度
解法一、dfs搜索（坑）
1 #include<iostream> 2 #include<cstdio> 3 #define ll long long 4 int n,a[1001],ans=0; 5 void dfs(int c,int now,int len) 6 { 7 if(c==n) 8 { 9 if(len>ans) ans=len; 10 return; 11 } 12 for(int i=c;i<=n;i++) 13 { 14 if(a[i]>now) dfs(i,a[i],len+1); 15 } 16 } 17 int main() 18 { 19 scanf("%d",&n); 20 for(int i=1;i<=n;i++) 21 { 22 scanf("%d",&a[i]); 23 } 24 dfs(1,-1,0); 25 printf("%d",ans); 26 return 0; 27 }
我就提一句，dfs中c代表的是當前狀態，即目前處理到的數，now代表前一個採用了的數，ans代表當前狀態的上升序列長度，最後比較每一個ans，找出最大的即可
但是很遺憾，人家太慢了。就過了兩個點。。。
那我還是講講其他的方法吧
解法二、記憶化搜索
不算很難
直接上核心程式碼理解一下吧，畢竟人家不是咱的重點關注對象
f[1][1]=a[1][1]; for(int i=2;i<=n;i++){ for(int j=1;j<=i;j++) f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]; } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,f[n][i]); cout<<ans;
正統解法，解法三：DP
用倒推正推都可以
①正推（其實就是 fk[x] =min{ fk-1[yi] +d [yi,x]}的一個載體）
1 #include<cstdio> 2 #define ll long long 3 using namespace std; 4 int n,a[1001],f[1001],p[1001]; 5 int main() 6 { 7 scanf("%d",&n); 8 for(int i=1;i<=n;i++) 9 { 10 scanf("%d",&a[i]); 11 } 12 f[1]=1; 13 for(int i=2;i<=n;i++) 14 { 15 f[i]=0; 16 for(int j=1;j<i;j++) 17 { 18 if(a[j]<a[i]&&f[j]>f[i]) 19 { 20 f[i]=f[j]; 21 p[i]=j; 22 } 23 } 24 f[i]++; 25 } 26 int ans=f[1],k=1; 27 for(int i=2;i<=n;i++) 28 { 29 if(f[i]>ans)ans=f[k=i]; 30 } 31 printf("%d",ans); 32 return 0; 33 }
啥意思呢，是這樣的
首先我們要明確我們定義的三個數組分別代表著啥：
a數組代表我輸入的數組，f[i]數組代表i對應的最長子上升子序列長度，p數組用於表示f[i]的最優值j的位置上，就是它的上一個既滿足在它前面，又比他小的數，然後我們可以舉個例子：
比如 ： 1 4 3
首先 i 等於2，也就是從第2個數 4 開始，我們讓f[1]等於1（等會你就知道為啥了），再用一個 j ，他的範圍是 [1,i），也就是找 i前面的數，那這裡由於j<i,所以 j 就只能等於1，那a[j]就等於1，我們判斷一下，如果a[j]<a[i]而且f[j]>f[i]，那我們就讓i的長度變成j的長度，並讓p[i]=j，結束後 i 變成3，j從0到1開始遍歷，是0的時候，a[j]代表1，a[i]等於3，由於滿足a[j]<a[i]而且f[j]（它就是 f[1]==1）>f[i]（==0），咱就進行一下操作：讓f[i]=f[j]=1,i的前驅（q[i]）=j=1;再輪到j=2,由於不滿足a[j]<a[i]，無法進行以下操作，所以不管他，那麼現在我就又有了a[3]的前驅，重複以上操作，我們就得到了最優解，和他們所對應的前驅，自然就可以得到最長上升子序列啦！！！
為啥要這樣？？
原因是我們要找的是最長上升子序列，所以前面的數a[j]必須比後面的數a[i]大（a[j]<a[i]），而且 j 對應的序列長度應該大於 i 對應的，原因是我們想讓最長的變成i所對應的長度，所以只有在 j 對應的長度比i對應的長度長的時候我才交換他們的長度，以保證 f[i]對應的是最大值，
p[i]=j 表示的是 i 的上一個即在它前面有比他小的數是 j（類似於它的前驅），我們把他記錄下來，目的是便於最後輸出。
最後讓f[i]的長度加1，因為我們這些數每遇到一個就會加1，殊不知其實一開始只有一個數的時候長度為0，所以最後加1才是最終的長度。
倒序也一樣：（ fk[x ]= min{ fk+1[yi]+d [x,yi]}）
1 //最長上升子序列（逆推） 2 #include<iostream> 3 #include<cmath> 4 using namespace std; 5 int a[1001]; 6 int f[1001];//對應的最長上升子序列長度 7 int p[1001]; 8 int ans; 9 //p數組用於記錄 f[i]的最優值j的位置 ，就是它的上一個既滿足在他前面有比他小的數， 10 int main() 11 { 12 int n; 13 cin>>n; 14 for(int i=1;i<=n;i++) cin>>a[i]; 15 f[n]=1;p[n]=0; 16 for(int i=n-1;i>0;i--) 17 { 18 f[i]=0; 19 for(int j=i+1;j<=n;j++) 20 { 21 if(a[i]<=a[j]&&f[j]>f[i]) 22 //兩個條件：1.j對應的數比i大（保證上升）2.j的長度要大於i的長度，要不換他幹啥 23 { 24 f[i]=f[j];//讓i的長度變成j的長度 25 p[i]=j;//記錄下來他的上一個即在它前面，又比他小的數，方便最後輸出 26 } 27 } 28 f[i]++; 29 } 30 ans=f[1]; 31 int k=1; 32 for(int i=2;i<=n;i++) 33 { 34 if(f[i]>ans) ans=f[k=i];//好高級 35 } 36 cout<<ans<<endl;//這是最長上升子序列長度 37 while(k>0) 38 { 39 cout<<a[k]<<" "; 40 k=p[k]; 41 } 42 return 0; 43 }
道理跟正推就是一樣的
說了這麼多了，總結一下吧
其實不難發現，我們會把一個大問題分成無數個小問題，但是他有一個前提。就是子問題的局部最優會導致整個問題的全局最優，也就是說無論過去我是咋決策的，現在的最優決策都是由原來的子問題的最優決策構成的，那也就是說一旦我們解決了子問題的最優，那以後的較大規模的問題也就迎刃而解了，而且一個問題的最優解只會受上一個最優子問題的影響，其他的子問題非最優解對現在的問題沒有任何影響！
這就是老師講的最優化原理和無後效性。
那我就思考了一下我剛才提及到的最長上升子序列是怎麼體現出這個特點的呢？？（僅個人觀點）
仔細想想，其實我一開始就記錄了每一個數的前驅，即它的上一個既滿足在它前面，又比他小的數。我雖然全都記錄下來了，但是我們只將最後我們得出的最長上升子序列的每個元素和其對應的前驅輸出，而不是把每個元素對應的前驅全都輸出，也就是錯誤的（不滿足條件的）我就不輸出了，這就保證了我的沒滿足全局最優的數並不會影響我們最後滿足條件的數列，這就滿足了DP的基本特徵（條件），即無後效性，所以才可以用DP來做這道題。
還有就是，做這道題的思路是這樣的：
1、劃分階段（在最長上升子序列一題中就是指的 i 和 j 對應的每一個階段吧）
2、確定狀態和變數（在這一題中我們運用了三個數組，分別表示 a[]原始數列、f[i] ：i對應的最長子序列長度、g[i]: f[i]的最優值j的位置 ，就是它的上一個既滿足在他前面有比他小的數）
3、確定狀態轉移方程
4、找出邊界條件（這裡就是 i 到頭就行）
T3、坐標DP
一般就是個二維數組，，，
比如這道摘花生的題，說是一片地，一些坐標上有花生，現在你在左上角，只能向右或向下移動，問你一路上能摘多少花生？
我們肯定要先建一個二位數組記錄每個點花生的數量（沒有那肯定就是0啊），那我現在就想寫出狀態轉移方程，怎麼思考？
反正我到一個點要不就是從上面下來要不就是從左邊往右走，那我們就比較上面的摘花生個數和左面總共摘得的花生個數，取最大值在加上這個點摘得的花生數量就是到這個點後你所最多能摘的花生數，即
f[i,j]=max{ f[i-1 , j],f[ i , j-1] } + a[i,j]，
這樣再用一個遞推就能實現了。那我們想，我們所得到的目前階段的最大值，肯定是不會受非最優子階段的影響。所以是可以用DP做的。
也整理了最近做過的幾道題
T4、
題目講的就是在一個數組中找到某幾個連續的數使得它們的和最大，針對這樣的題，當然使用DP啦
先輸入他們，f[i]數組代表是 i 狀態時的最好方案（最大的和），值得注意的是，f[1]的狀態就是a[i]，因為就他一個。，我們現在的主要任務就是尋找此問題的狀態轉移方程，
仔細想想，我們會發現，我們想要求得的第i個狀態的最好方案無非就兩種，要麼加他，要麼不加他，再取個max就好了。
得到：f[i]=max(f[i-1]+a[i],a[i])
下面就順水推舟的出來了
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 int a[1000001]; 5 int f[1000001]; 6 int maxn=-1; 7 int main() 8 { 9 int n; 10 cin>>n; 11 for(int i=1;i<=n;i++) 12 { 13 cin>>a[i]; 14 } 15 f[1]=a[1]; 16 for(int i=1;i<=n;i++) 17 { 18 f[i]=max(f[i-1]+a[i],a[i]); 19 maxn=maxn>f[i]? maxn:f[i]; 20 } 21 cout<<maxn; 22 return 0; 23 24 }
T5、
求兩個序列的最長公共子串的長度，這個子串要求在序列中是連續的
只要找到我們想要的狀態轉移方程就好，關鍵就是咋想呢？？
我先遍歷每一個數組元素，將其分為兩種情況，其中一種就是兩個元素不相同的，我直接continue進行下一個就好，對於兩者相同的，其長度不就是兩個元素各自的數組中其前一個數的長度再加1嗎，那方程就自然而然的推出來了：f[i][j]=f[i-1][j-1]+1，然後我們只要比較每一個f[i][j],取他們的最大值就好了
程式碼如下
#include<iostream> #include<cstdio> using namespace std; char a[1001],b[1001]; int f[1001][1001]; int ans; int main() { int m,n; cin>>m>>n; for(int i=1;i<=m;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { cin>>b[i]; } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(a[i]==b[j]) { f[i][j]=f[i-1][j-1]+1; ans=max(ans,f[i][j]); } } } cout<<ans; return 0; }
還有就是關於數字金字塔啥的，其實都一樣，找出它的狀態轉移方程就好了，比如金字塔那玩意，想要在金字塔的上面走一條路使得經過的數字之和最大，我們只要用過列出狀態轉移方程（直接看程式碼吧，不啰嗦了，就是這個數它上面的和左上的f的max再加上自己就好了），得到每個金字塔最低端的終點，再比較哪個終點的f最大就輸出，然後就開開心心地A掉了
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 int a[1001][1001]; 5 int f[1001][1001]; 6 int ans; 7 int main() 8 { 9 int n; 10 cin>>n; 11 for(int i=1;i<=n;i++) 12 { 13 for(int j=1;j<=i;j++) 14 { 15 cin>>a[i][j]; 16 } 17 } 18 f[1][1]=a[1][1]; 19 for(int i=2;i<=n;i++) 20 { 21 for(int j=1;j<=i;j++) 22 { 23 f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]; 24 } 25 } 26 for(int i=1;i<=n;i++) 27 { 28 ans=ans>f[n][i]? ans:f[n][i]; 29 } 30 cout<<ans; 31 return 0; 32 }
。。。。。。。
其實還有很多很多很難很難的題，小生孤陋寡聞，才疏學淺，這裡就不再體現，以後會查缺補漏，日臻完善的！！
我就記錄到這了，再見！！
2022/3/17
