动态规划

动态规划，建立一个辅助数组dp，记录花i块钱要用的最少张数，每次输入一个arr，就将dp[arr]设置为1，然后从arr+1到aim开始更新数组dp，方程为dp[j] = min(dp[j], dp[j-arr]+1);
代码如下：

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

int main()
{
    int n,aim;
    cin >> n >> aim;

    vector<int> dp(aim + 1, INT_MAX);
    dp[0] = 0;
    int arr = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> arr;
        dp[arr] = 1;//当有arr值面值的钱，当然最少张数对应的就是1
        for(int j = arr + 1; j <= aim; j++)
        {
            dp[j] = min(dp[j], dp[j-arr] + 1);//这个过程会更新arr倍数面值的钱，例如dp[n*arr]最后一定会是n；
        }
    }
    if (dp[aim] == INT_MAX)
    {
        cout << -1 <<endl;
    }
    else
    {
        cout << dp[aim] << endl;
    }

    return 0;
}