d904:換零錢

題目

https://zerojudge.tw/ShowProblem?problemid=d904

解題思路

1. dp
2. 把值一路跑過去 (image credit:碁峰資訊)

注意的地方

1. c,n分別代表的意義，不要寫反!
2. w的陣列大小要1000*10(+1)–w[10001]

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
  
  int c,n;//要給的錢總值、硬幣種類數
  int a[11]={},w[10001]={};//幣值、錢的總值
  while(cin>>c>>n){
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    memset(w,0x6f,sizeof(w));
    w[0]=0;
    for(int i=0;i<n;i++){
        for(int j=a[i];j<=c;j++){
            if(w[j-a[i]]+1<w[j]){
                w[j]=w[j-a[i]]+1;
            }
        }
    }
    cout<<w[c]<<endl;
  } 
}