DP 即動態規劃（Dynamic Programming），是一種通過把原問題分解為相對簡單的子問題，并保存子問題的解來避免重復計算，從而解決復雜問題的算法策略。以下從幾個方面簡述動態規劃：
基本思想
動態規劃的核心在于 “分治” 和 “最優子結構”。它將一個復雜問題分解為一系列相互關聯的子問題，通過求解子問題并保存其解，避免對相同子問題的重復求解，從而減少計算量。同時，原問題的最優解可以由子問題的最優解組合而成，這就是最優子結構性質。
適用條件
- 最優子結構性質：問題的最優解包含其子問題的最優解。即可以通過子問題的最優解推導出原問題的最優解。例如，在背包問題中，對于一個容量為?
W?的背包和?n?個物品，要得到其最優裝法，可以先考慮容量為?W - w[i]（w[i]?為第?i?個物品的重量）的背包和前?n - 1?個物品的最優裝法。 - 子問題重疊性質：在求解過程中，會多次遇到相同的子問題。動態規劃通過保存子問題的解，避免了對這些子問題的重復計算，從而提高了效率。比如在斐波那契數列的計算中，直接遞歸計算會有大量重復的子問題計算，而使用動態規劃可以避免這種情況。
求解步驟
- 定義狀態：明確問題的狀態表示，即如何用一個或多個變量來描述子問題。例如，在最長上升子序列問題中，可以定義狀態?
dp[i]?表示以第?i?個元素結尾的最長上升子序列的長度。 - 確定狀態轉移方程：根據問題的最優子結構性質，找出狀態之間的轉移關系。狀態轉移方程描述了如何從子問題的解推導出原問題的解。例如，在最長上升子序列問題中，狀態轉移方程為?
dp[i] = max(dp[j] + 1) (0 <= j < i 且 a[j] < a[i])。 - 初始化：確定初始狀態的值，這些初始狀態是問題的邊界條件。例如，在斐波那契數列的動態規劃求解中，
dp[0] = 0，dp[1] = 1?就是初始狀態。 - 計算順序：根據狀態轉移方程，確定計算狀態的順序，一般是從簡單的子問題開始，逐步求解更復雜的問題。
應用場景
動態規劃在很多領域都有廣泛的應用，常見的問題包括：
- 背包問題：如 0 - 1 背包問題、完全背包問題等，用于在一定的約束條件下選擇物品，使得總價值最大。
- 最長公共子序列問題：找出兩個序列中最長的公共子序列，在生物信息學、版本控制等領域有應用。
- 最短路徑問題：如 Floyd - Warshall 算法，用于求解圖中任意兩點之間的最短路徑。
- 資源分配問題：在多個項目或任務之間分配資源，以達到最優的效益。
目錄
1087
題目
思路
代碼詳細步驟
動態規劃初始化
狀態轉移
找出最大值
代碼
1203
題目
思路
代碼
1003
題目
思路
代碼
1087
題目
思路
動態規劃算法的核心在于將原問題分解為一系列子問題，并通過求解子問題來得到原問題的解。在這個問題中，我們定義狀態?dp[i]?表示以第?i?個元素結尾的最長上升子序列的最大和。通過遍歷序列中的每個元素，我們可以根據之前的狀態來更新當前狀態，最終找出所有狀態中的最大值，即為最長上升子序列的最大和。
代碼詳細步驟
動態規劃初始化
dp[0]=a[0];：將?dp[0]?初始化為?a[0]，因為以第一個元素結尾的最長上升子序列就是它本身，其和就是?a[0]。狀態轉移
- 外層循環?
for(int i = 1; i < n; i++)：遍歷數組中的每個元素，從第二個元素開始。dp[i]=a[i];：將?dp[i]?初始化為?a[i]，表示以第?i?個元素結尾的最長上升子序列至少包含該元素本身。- 內層循環?
for(int j = 0; j < i; j++)：遍歷當前元素?a[i]?之前的所有元素。if(a[i]>a[j])：判斷?a[i]?是否大于?a[j]，如果滿足條件，說明可以將?a[i]?接到以?a[j]?結尾的最長上升子序列后面。dp[i]=max(a[i]+dp[j],dp[i]);：更新?dp[i]?的值，取?a[i] + dp[j]?和?dp[i]?中的最大值。a[i] + dp[j]?表示將?a[i]?接到以?a[j]?結尾的最長上升子序列后面得到的新子序列的和。找出最大值
int maxnum=-1e9;：將?maxnum?初始化為一個較小的值?-1e9，確保后續找到的任何?dp[i]?值都能更新?maxnum。for(int i = 0; i < n; i++){ maxnum=max(maxnum,dp[i]); }：遍歷?dp?數組，找出其中的最大值。
代碼
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1010],a[1010],n;
int main(){while(cin>>n&&n){for(int i=0;i<n;i++){cin>>a[i];}dp[0]=a[0];for(int i=1;i<n;i++){dp[i]=a[i];for(int j=0;j<i;j++){if(a[i]>a[j]){dp[i]=max(a[i]+dp[j],dp[i]);}}}int maxnum=-1e9;for(int i=0;i<n;i++){maxnum=max(maxnum,dp[i]);}cout<<maxnum<<endl;}return 0;
}1203
題目
思路
外層循環?
for(int i = 0; i < m; i++)：遍歷每一個物品。內層循環?
for(int j = n; j >= a[i]; j--)：從背包的總容量?n?開始，倒序遍歷到當前物品的重量?a[i]。倒序遍歷是為了保證每個物品只被選擇一次，這是 0 - 1 背包問題的常見處理方式。狀態轉移方程?
dp[j]=max(dp[j],dp[j-a[i]]+prob[i]-dp[j-a[i]]*prob[i]);：
dp[j]?表示不選擇當前物品?i?時，背包容量為?j?的最大成功概率。
dp[j - a[i]]?表示在不放入當前物品?i?時，背包容量為?j - a[i]?的最大成功概率。
dp[j - a[i]] + prob[i] - dp[j - a[i]] * prob[i]?表示選擇當前物品?i?時的成功概率。這里基于概率的計算原理，假設物品的成功是相互獨立事件，使用公式?P(A 或 B) = P(A) + P(B) - P(A) * P(B)?來計算選擇當前物品后的成功概率。通過?
max?函數取兩者中的最大值更新?dp[j]。
代碼
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
double dp[N];
double prob[N];
int a[N];
int n,m;
int main(){while(cin>>n>>m){if(n==0 && m==0) break;for(int i=0;i<m;i++){cin>>a[i]>>prob[i];}memset(dp,0,sizeof(dp));for(int i=0;i<m;i++){for(int j=n;j>=a[i];j--){dp[j]=max(dp[j],dp[j-a[i]]+prob[i]-dp[j-a[i]]*prob[i]);}}printf("%.1lf%%\n",dp[n]*100);}return 0;
}1003
題目
思路
狀態轉移方程?
dp[j]=max(dp[j],dp[j-a[i]]+prob[i]-dp[j-a[i]]*prob[i]);：
dp[j]?表示不選擇當前物品?i?時，背包容量為?j?的最大成功概率。
dp[j - a[i]]?表示在不放入當前物品?i?時，背包容量為?j - a[i]?的最大成功概率。
dp[j - a[i]] + prob[i] - dp[j - a[i]] * prob[i]?表示選擇當前物品?i?時的成功概率。這里基于概率的計算原理，假設物品的成功是相互獨立事件，使用公式?P(A 或 B) = P(A) + P(B) - P(A) * P(B)?來計算選擇當前物品后的成功概率。通過?
max?函數取兩者中的最大值更新?dp[j]。
代碼
#include<iostream>
using namespace std;
int n,m,l,r,maxnum,sum,temp,num;
int main(){cin>>n;for(int i=0;i<n;i++){l=0,r=0,temp=1,maxnum=-20000,sum=0;cin>>m;for(int j=1;j<=m;j++){cin>>num;sum+=num;if(sum>maxnum){r=j;maxnum=sum;l=temp;}if(sum<0){temp=j+1;sum=0;}}cout<<"Case "<<(i+1)<<":"<<endl<<maxnum<<" "<<l<<" "<<r<<endl;if(i<n-1) cout<<endl;}return 0;
}
)
