算法设计与分析-Week12

发表于 | 更新于

Coin Change

题目描述

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

解题思路

本题给出了硬币的面值，要求用最少的硬币组成一个数，组不成就返回-1.
首先声明一个大小为amount+1的数组fewestCoins，fewestCoins[i]表示组成数字i所需的最少硬币数，组不成则为-1，最后fewestCoins[amount]即为所求。将数组的第一个元素初始化为0，因为使用0个硬币就能组成0这个数，其余元素初始化为最大正整数。状态转移为fewestCoins[i] = min(fewestCoins[i], fewestCoins[i - coins[j]] + 1),其中coins[j]为硬币面值，若没有更新fewestCoins[j]，则将其置为-1。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount <= 0) return 0;
        vector<int> fewestCoins(amount + 1, INT_MAX);
        fewestCoins[0] = 0;
        int n = coins.size();
        bool found = false;
        for(int i = 1; i <= amount; i++) {
            found = false;
            for(int j = n - 1; j >= 0; j--) {
                if(coins[j] <= i && fewestCoins[i - coins[j]] != -1) {
                    fewestCoins[i] = min(fewestCoins[i], fewestCoins[i - coins[j]] + 1);
                    found = true;
                }
            }
            if(!found) fewestCoins[i] = -1;
        }
        return fewestCoins[amount];
    }
};
0%