题解 | #换钱的最少货币数#

思路：动态规划，建立aim+1位的数组f，f[i]表示i元所需最小张数。初始都赋值为-1，0位置的值为0.进行动态规划，对于每一个位置i，遍历面值数组，i减去面值在f数组范围内且可达(即f对应位置不为-1)则更新数组f。

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,aim,temp;
    cin>>n>>aim;
    vector<int> nums;
    while(n--){
        cin>>temp;
        nums.emplace_back(temp);
    }
    vector<int> f(aim+1,-1);
    f[0]=0;
    n=nums.size();
    for(int i=1;i<=aim;++i){
        for(int j=0;j<n;++j)
            if(i-nums[j]>=0&&f[i-nums[j]]!=-1)
                if(f[i]==-1) f[i]=f[i-nums[j]]+1;
                else f[i]=min(f[i],f[i-nums[j]]+1);
    }
    cout<<f[aim];
}