【题解】换钱的最少货币数

表示组成 价值需要的最少的货币数
如果目前情况下价值目前最少能由 个货币组成，那么加了一个 价值的商品，就可以由个货币组成
对于每一个物品，从循环一遍，更新dp的值。所有的物品都加入完毕以后，就是结果。

#include<iostream>

using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
    int n,m;
    cin >> n >> m;
    int arr[1010],dp[5010]={0};
    for(int i = 0 ; i < n ; i++)
    {
        cin >> arr[i];
    }
    for(int i = 1 ; i <= m ; i++)
    {
        dp[i]= INF;
    }
    for(int i = 0 ; i < n ; i++)//对每个物品进行遍历
    {
        for(int j = 0 ; j <= m-arr[i] ; j++)//对每个价值进行遍历
        {
            if(dp[j]!=INF)
            {
                dp[j+arr[i]] = min(dp[j+arr[i]],dp[j]+1);
            }
        }
    }
    if(dp[m]==INF){cout<<"-1"<<endl;}
    else cout<<dp[m]<<endl;
    return 0;
}