题解 | #兑换零钱（一）#

类似背包但又不是背包，涨知识了

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
      //  为0，无需货币
      if (aim <= 0) {
        return 0;
      }
      
      //  不为0，但是钱包为空，无解
      if (arr.empty()) {
        return -1;
      }
      
      //  dp[i] 表示i元所需要的最小货币数
      //  初始值设定有点费劲
      std::vector<int> dp(aim + 1, aim + 1);
      dp[0] = 0;
      
      for (int i = 1; i <= aim; ++i) {
        for (int j = 0; j < arr.size(); ++j) {
          if (arr[j] <= i) {
            //  每一次货币数最大都不可能超过aim+1，超过即为无解
            dp[i] = std::min(dp[i], dp[i - arr[j]] + 1);
          }
        }
      }
      
      //  1元是最小货币，也就是dp[aim]货币数 最大为aim，超过则无解
      return dp[aim] > aim ? -1 : dp[aim];
    }
};