题解 | #兑换零钱(一)#

#include <climits>
#include <cstdint>
#include <sys/types.h>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        if(!arr.size())return -1;
        // write code here
        uint_fast16_t dp[aim + 1];
        int i=0,j,t=1;
        fill(dp+1,dp+aim+1,5001);
        dp[0]=0;
        for(i=0;i<arr.size();++i){
            for(j=1;j<=aim;++j){
                //cout<<j<<' '<<arr[i]<<' '<<j-arr[i]<<endl;
                if(arr[i]<=j)dp[j]=min(dp[j],dp[j-arr[i]]+1);
                //cout<<dp[i][j]<<' ';
            }
        }


        return dp[aim]==5001?-1:dp[aim];
    }
};

很经典，随便存一下……