? ? ? ?動態規劃算法通常基于一個遞推公式及一個或多個初始狀態。 當前子問題的解將由上一次子問題的解推出。使用動態規劃來解題只需要多項式時間復雜度， 因此它比回溯法、暴力法等要快許多。動態規劃也是面試筆試題中的一個考查重點，當閱讀一個題目并且開始嘗試解決它時，首先看一下它的限制。 如果要求在多項式時間內解決，那么該問題就很可能要用DP來解。遇到這種情況， 最重要的就是找到問題的“狀態”和“狀態轉移方程”。(狀態不是隨便定義的， 一般定義完狀態，你要找到當前狀態是如何從前面的狀態得到的， 即找到狀態轉移方程)如果看起來是個DP問題，但你卻無法定義出狀態， 那么試著將問題規約到一個已知的DP問題。

這里先說明一個最簡單的動態規劃實例：硬幣問題。后續還會給出更多的實例，例如：最長公共子序列，最長公共子串，最長遞增子序列，字符串編輯距離等。動態規劃的關鍵就是找出“狀態”和“狀態轉移方程”。

硬幣問題：給你一些面額的硬幣，然后給你一個值N，要你求出構成N所需要的最少硬幣的數量和方案。分析：這個問題可以嘗試用貪心算法去解決，先從面額最大的硬幣開始嘗試，一直往下找，知道硬幣總和為N。但是貪心算法不能保證能夠找出解（例如，給,2,3,5,然后N=11）。我們可以換個思路，我們用d(i)表示求總和為i的最少硬幣數量（其實就是動態規劃中的“狀態”）,那么怎么從前面的狀態（并不一定是d(i-1)這一個狀態）到d(i)這個狀態？假設硬幣集合為coins[0~N]，在求d(i)之前，我們假設d(1~i-1)全部都求出來了，那么d(i)=min{d(j)+1},if i-j 在coins中（其實這就是“狀態轉移方程”）。另?我們把每種面值看作一個點！表示“還需要湊足的面值”，初始狀態為S，目標狀態為0。那么若當前狀態在i，每使用一個硬幣j，狀態便轉移到i-Vj。

舉例說明：coins={2,3,5}，N=11。

d(0)=0;

d(1)=0;

d(2)=d(0)+1=1;

d(3)=d(0)+1=1;

d(4)=d(2)+1=2;

d(5)=min{d(3)+1,d(2)+1,d(0)+1}=1;

d(6)=min{d(4)+1,d(3)+1}=2;

.......................

同時為了求出最后的方案（不僅僅是硬幣個數），需要記錄求每個狀態選擇的“路徑”，例如:求d(5)我們選擇了d(0)+1，那么我們選擇的路徑就是5-0=5。我們必須記錄這些路徑，然后根據路徑得出結果。對于d(6)，我們開始選擇了3,也就是說我們選擇了從d(3)狀態和硬幣3跳轉到d(6),接著對于d(3)，我們選擇了3，也就是說我們選擇了從d(0)狀態和硬幣3跳轉到了d(3)，接著對于d(0)，這個是初始狀態。所以我們得方案是3,3。

遞推（打印最小序）：?

#include <iostream> #include <cstring>using namespace std;const int MAXN = 10000; const int INF = 1000000000; int n, S, V[MAXN], minn[MAXN], maxn[MAXN]; //minn[i]表示還需湊足價值為i的話，所需的最少的硬幣數目！maxn[i]表示還需湊足價值為i的話，所需的最多的硬幣數目！void print_ans(int* d, int S) {for(int i = 1; i <= n; ++i) {if(S >= V[i] && d[S] == d[S - V[i]] + 1){ //從小到大尋找滿足條件的那個點！cout << i << " ";print_ans(d, S-V[i]);break; //這個不能忘記！}} }int main() {cin >> n >> S;for(int i = 1; i <= n; ++i) {cin >> V[i];}for(int i=1; i<=S; ++i){minn[i]=INF;maxn[i]=-INF;}for(int i=1; i<=S; ++i)printf("minn=%d\n",minn[i]);for(int i = 1; i <= S; ++i) { //遞推！求出所有minn[1...S]與maxn[1...S]！for(int j = 1; j <= n; ++j) {if(i >= V[j]) {minn[i] = min(minn[i], minn[i - V[j]] + 1);maxn[i] = max(maxn[i], maxn[i - V[j]] + 1);}}}cout << minn[S] << endl;cout << maxn[S] << endl;print_ans(minn, S);cout << endl;print_ans(maxn, S);cout << endl;return 0; }
另一種打印方式：

#include <iostream> #include <string> using namespace std;const int MAXN = 10000; const int INF = 1000000000; int n, S, V[MAXN], minn[MAXN], maxn[MAXN]; //minn[i]表示還需湊足價值為i的話，所需的最少的硬幣數目！maxn[i]表示還需湊足價值為i的話，所需的最多的硬幣數目！ int min_coin[MAXN], max_coin[MAXN]; //min_coin[S]記錄的是滿足minn[S] = minn[S-V[i]]+1的最小的i。void print_ans(int* d, int S) {while(S) {cout << d[S] << " ";S -= V[d[S]];} }int main() {cin >> n >> S;for(int i = 1; i <= n; ++i) {cin >> V[i];}for(int i=1; i<=S; ++i){minn[i]=INF;maxn[i]=-INF;}for(int i = 1; i <= S; ++i) { //遞推！求出所有minn[1...S]與maxn[1...S]！for(int j = 1; j <= n; ++j) {if(i >= V[j]) {if(minn[i] > minn[i - V[j]] + 1) {minn[i] = minn[i - V[j]] + 1;min_coin[i] = j;}if(maxn[i] < maxn[i - V[j]] + 1) {maxn[i] = maxn[i - V[j]] + 1;max_coin[i] = j;}}}}cout << minn[S] << endl;cout << maxn[S] << endl;print_ans(min_coin, S);cout << endl;print_ans(max_coin, S);cout << endl;return 0; }

總結

以上是生活随笔為你收集整理的DP_硬币问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。