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

class Solution {
  public:
    int minMoney(vector<int>& arr, int aim) {
        if (!aim) return 0;
        if (arr.empty()) return -1;
        int lenarr = arr.size();
        vector<int> dp(aim, 1e9);
        for (int j = 0; j < lenarr; j++) {
            for (int i = arr[j] - 1; i < aim; i++) { //外循环遍历arr，内循环遍历[arr[j]-1,aim]可以跳过一些小于arr[j]的数
                if (i + 1 == arr[j]) {
                    dp[i] = 1;
                } else {
                    if (i - arr[j] >= 0) {
                        if (dp[i - arr[j]] != -1) {
                            dp[i] = dp[i - arr[j]] + 1 < dp[i] ? dp[i - arr[j]] + 1 : dp[i];
                        }
                    }
                }
            }
        }
        if (dp[aim - 1] == 1e9) {
            dp[aim - 1] = -1;
        }
        return dp[aim - 1];
    }
};