# DP
dynamic programming(動態規劃)

## 01背包問題

對於每個物品可選與不選,先利用這點找出轉移方程,當然我們要選出最大值,所以在此選擇裡選出的最大值就是該項目答案

int chose=dp(n-1,w-L[n])+S[n];  
//選此項目,加上該項目的利益
int notchose=dp(n-1,w);  
//不選此項目,=前一個項目的答案

return max(chose,notchose); 

接著再利用紀錄重複子問題的答案,加速該題的計算過程

if(dpa[n][w]!=0) return dpa[n][w]; 

int chose=dp(n-1,w-W[n])+P[n];  
int notchose=dp(n-1,w); 

dpa[n][w]=max(chose,notchose);  
return dpa[n][w];

最後再加上邊界判斷的判斷就完成了

int dp(int n,int w){  
    if(w<0) return -1e9;  
    if(n==0) return 0;  
    
    if(dpa[n][w]!=0) return dpa[n][w]; 
    
    int chose=dp(n-1,w-W[n])+P[n];  
    int notchose=dp(n-1,w); 
    
    dpa[n][w]=max(chose,notchose);  
    return dpa[n][w];  
}  

由遞迴式(top-down)轉變成迴圈式(botton-up)

for(int n=1;n<=N;n++){  
    for(int w=0;w<=M;w++){  
        int chose;       
    
        if(w-W[n]>=0) chose=dp[n-1][w-W[n]]+P[n];  
        else chose=INT_MIN;
        //如果背包放不下此物品,就不能選,要給他一個很小的值這樣取max才不會取到
        int notchose=dp[n-1][w];  
        
        dp[n][w]=max(chose,notchose);  
    }  
 }

簡化為一為陣列
因為每次會需要左上方的陣列,如果從前面掃的話會會把後面要存取的數值覆蓋掉,所以要從後面掃

for(int n=1;n<=N;n++){  
    for(int w=M;w>0;w--){  
      int chose=-1e9;  
      if(w-W[n]>=0) chose=dp[w-W[n]]+P[n]; 
      
      int notchose=dp[w];  
      
      dp[w]=max(chose,notchose);  
    }  
}

如果放進去了哪些物件可以逆推回去

int BigM=M;
int ans[10000]={0};  //紀錄有沒有放進去

for(int i=N;i>0;i--){
    if(BigM-W[i]>=0 && dp[i][BigM]==dp[i-1][BigM-W[i]]+P[i]){
      ans[i]=1;  //記錄這個放進去物件的點
      BigM-=W[i];  //扣掉此物件的重量繼續找下一個物品
    }
}

for(int i=1;i<=N;i++){
    if(ans[i]) cout << L[i] << " ";
}

一維陣列如果要求哪些元素被放進去要開一個陣列記錄

bool ans[100][100]={0};  //紀錄有沒有放進去

for(int n=1;n<=N;n++){  
    for(int w=M;w>0;w--){  
        if(dp[w-W[n]]+P[n] > dp[w]){
            dp[w]=dp[w-W[n]]+P[n];
            ans[n][w]=true;  //第n項物品在w的時候有放進去         
        }
    }  
}

for(int i=N,BigM=M;i>0;i--){
    if(ans[i][BigM]){
        cout << i << " ";
        BigM-=W[i];
    }
}

## coin change(最少硬幣)

對於每個amount都可以是(amount-貨幣面額)的情況再+1,+1就是該貨幣面額,所以狀態轉移方程為

dp[i]=min(dp[i],dp(amount-coin[i])+1);

所以在初始化的時候可以把陣列設成amount+1,但不包刮dp[0] (因為在0元的時候能換到的情況是0),這樣在取min的時候如果有合法的情況都會比amount+1小,(能換到最多錢的情況是amount個1塊)),然後更新到dp裡面,最後要判斷有沒有任何方法可以換的時候就看dp[amount],如果dp[amount]跟我們初始化的值一樣代表沒有情況能成立,否則dp[amount]是最佳解

bottom-up

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1,amount+1);
    dp[0]=0;
    for(int i=1;i<=amount;i++){
        for(int j=0;j<coins.size();j++){
            if(i-coins[j]>=0) dp[i]=min(dp[i],dp[i-coins[j]]+1);
        }
    }
    return dp[amount]>amount?-1:dp[amount];
}

Top-down

int dpf(int amount,vector<int>& cache){
    if(amount<0) return 1e9;
    if(amount==0) return 0;

    if(cache[amount]) return cache[amount];

    int mi=amount+1;
    for(int i=0;i<coin.size();i++){
        mi=min(mi,dpf(amount-coin[i],cache)+1);
    }
    return cache[amount]=mi;
}

## coin change(幾種組合)
dp[i]項的組合數就是dp[i-c]的組合相加,c = for c in range coin,要注意兩個迴圈內外的順序,如果是對於第i個點一次跑完所有硬幣的時候,後面會因為重複的組合而導致答案錯誤,例如3={2,1}&{1,2},所必需把該硬幣拷完才換下一個,否則會出現只有順序顛倒但元素卻一樣的組合

d253. 00674 - Coin Change
AC (22ms, 368KB)

#include <bits/stdc++.h>
using namespace std;

int coin[]={1,5,10,25,50};
int coinsize=5;

int main(){
  int n;
  vector<int> dp(7490,0);
  dp[0]=1; 
  for(int j=0;j<coinsize;j++){
    for(int i=1;i<=7489;i++){
      if(i-coin[j]>=0){
        dp[i]+=dp[i-coin[j]];
      }
    }
  }
  while(cin >> n){
    cout << dp[n] << '\n';
  }
  return 0;
}

另外特別注意的點是內迴圈數值的順序:

如果coin裡的元素是可以重複的,內詢圈的順序要從小到大,因為這樣才會把小的帶到大的;

如果coin裡的元素不能重複,內迴圈要從大跑到小,這樣才不會把小的已算過的該元素再算到大的,這樣就會算兩次;

(左邊元素可重複,右邊元素不可重複)