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

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

#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;
}