LeetCode Solutions

Appearance

322. 零钱兑换 ​

为保证权益，题目请参考 322. 零钱兑换(From LeetCode).

解决方案1 ​

CPP ​

C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;


// Method 1
//class Solution {
//public:
//    int coinChange(vector<int> &coins, int amount) {
//        vector<int> vec(amount + 1, INT_MAX / 10);
//        vec[0] = 0;
//        for (auto coin:coins) {
//            for (int i = coin; i < vec.size(); i++) {
//                vec[i] = min(vec[i], vec[i - coin] + 1);
//            }
//        }
//        return vec[amount] == INT_MAX/10 ? -1: vec[amount];
//    }
//};


// Method 2
class Solution {
public:
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX/10);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (auto coin: coins) {
                if (i - coin >= 0) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == INT_MAX/10 ? -1:dp[amount];
    }
};

int main() {
    return 0;
}

解决方案2 ​

CPP ​

C++
#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;

bool cmp(int a, int b)
{
    return a >= b;
}

class Solution
{
public:
    int ans = INT_MAX;
    int coinChange(vector<int> &coins, int amount)
    {
        if (amount == 0)
        {
            return 0;
        }
        sort(coins.begin(), coins.end(), cmp);
        coinChangeHelper(coins, amount, 0, 0);

        return ans == INT_MAX ? -1 : ans;
    }
    void coinChangeHelper(vector<int> &coins, int amount, int index, int count)
    {
        if (amount == 0)
        {
            ans = min(ans, count);
            return;
        }

        if (amount <= 0 || index == coins.size())
        {
            return;
        }

        for (int i = amount / coins[index]; i >= 0 && i + count <= ans; --i)
        {
            coinChangeHelper(coins, amount - i * coins[index], index + 1, count + i);
        }
    }
};

int main()
{
    Solution so;
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(5);

    cout << so.coinChange(vec, 11) << endl;
    return 0;
}