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

#include <algorithm>
#include <vector>
class Solution {
  public:
    int minMoney(vector<int>& arr, int aim) {
        if (!aim) return 0;
        if (arr.empty()) return -1;
        int lenarr = arr.size(), minarr = *min_element(arr.begin(), arr.end());
        vector<int> dp(aim, 0);
        int tmp;
        for (int i = 0; i < aim; i++) {
            if (i + 1 < minarr) { //小于最小货币面值
                dp[i] = -1;
            } else {
                tmp = (1 << 31) - 1; //int型最大值
                for (int j = 0; j < lenarr; j++) {
                    if (i + 1 == arr[j]) { //等于所给面值之一，即只需1张货币
                        dp[i] = 1;
                        break;
                    }
                    if (i - arr[j] >= 0) { 
                        if (dp[i - arr[j]] != -1) { //可以在前面记录的最少货币数基础上加一张货币
                            dp[i] = dp[i - arr[j]] + 1 < tmp ? dp[i - arr[j]] + 1 : tmp;
                            tmp = dp[i];
                        }
                    }
                }
                if (dp[i] == 0) { //不可兑换
                    dp[i] = -1;
                }
            }
        }
        return dp[aim - 1];
    }
};