DP（動態規劃）：
概念： 用來解決一類最優化問題的演算法思想，即 將一個復雜的問題分解成若干個子問題，通過綜合子問題的最優解得到原問題的最優解，DP會將每個求解程序的自問題的解記錄下來，下次碰到同樣的子問題時，就可以直接使用之前記錄的結果，而不是重復計算
總之：一個問題必須擁有重疊子問題和最優子結構，才能使用動態規劃去解決
2.動態規劃的遞回寫法
//斐波那契數列為例
int f(int n){
if(n==0||n==1) return 1;
else return f(n-1)+f(n-2);
}
/*這個遞回會涉及到很多重復的計算，比如n==5時，f(5)=f(4)+f(3),接下來計算f(4)時會有
f(4)=f(3)+f(2),所以f(3)會被重復計算，實際復雜度為O(2^n)
為了避免重復計算，開一個一維陣列dp保存已經計算過的結果，dp[n]記錄f(n)的結果 dp[n]=-1表示沒有被計算過*/
int f(int n){
if(n==0||n==1) return 1;
if(dp[n]!=-1) return dp[n];//說明已經計算過，直接回傳結果，無需重復計算
else{
dp[n]=f(n-1)+f(n-2);
return dp[n];
}
}
//復雜度降到了O(n)
*******:
如果一個問題可以被分解為若干個子問題，且這些問題會重復出現，那么就稱這個問題擁有
重疊子問題，動態規劃通過記錄重疊子問題的解，來使下次碰到相同的子問題時就直接使用
記錄的結果，避免大量重復計算，所以，一個問題必須擁有子問題，才能使用動態規劃
動態規劃的遞推寫法
數塔問題為例：
第n層有n個數字，現在從第1層走到第n層，每次只能走向下一層連接的兩個數字中的一個，問：最后將路徑上所有數字相加后得到的和最大是多少？
如果窮舉所有路徑，復雜度為O（2^n),會導致反復訪問，
可以在第一次列舉時把某個位置能到達底層的所有路徑的最大和記錄下來，再次訪問這個 位置時就可以直接獲取這個最大值
/*
令dp[i][j]表示從第i行第j個數字出發的到達最底層的所有路徑中能得到的最大和
dp[1][1]即最終答案
如果要求出dp[i][j]，那么一定要先求出它的兩個子問題--從位置(i+1,j)到達最
底層的最大和dp[i+1][j] 和 從位置(i+1,j+1)到達最底層的最大和dp[i+1,j+1],
即進行了一次決策：走位置(i,j)的左下還是右下，dp[i][j]就是dp[i+1][j+1]和
dp[i+1][j+1]的較大值加上f[i][j]，即為:
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
dp[i][j]稱為問題的狀態，把上面的式子稱作狀態轉移方程，把狀態dp[i][j]轉移為
dp[i+1][j]和dp[i+1][j+1],dp[i][j]的狀態只與第i+1層的狀態有關，與其他層狀
態無關，什么時候到頭呢，數塔的最后一層的dp值總是等于元素本省，把這種可以直
接確定結果的部分稱為邊界，動態規劃的遞推寫法總是從這些邊界出發，通過狀態轉
移方程擴散到整個dp陣列
從最底層各位置的dp值開始，不斷往上求出每一層各位置的dp值，最后就得到dp[1][1]*/
int f[1000][1000],dp[1000][1000]
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;<=i;j++) cin>>f[i][j];//讀入資料
}
//邊界dp值
for(int i=1;i<=n;i++) dp[n][i]=f[n][i];
//從第n-1層不斷往上計算dp[i][j]
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
//狀態轉移方程
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
}
}
cout<<dp[1][1];
return 0;
}
*******:
如果一個問題的最優解可以由其他子問題的最優解有效構造出來，那么稱這個問題擁有最優子結構，最優子結構保證動態規劃中原問題的最優解可以由子問題的最優解推倒出來，因此，一個問題必須擁有最優子結構，才能用動態規劃去解決
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57186.html
標籤：其他
下一篇：鏈表合并