Использование модуля для решения вопроса об изменении монеты

Question

Я ищу другой способ решить проблему замены монет с помощью модуля. Большинство решений касаются использования динамической памяти для решения этой проблемы.

Example: 

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.

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

Цель состоит в том, чтобы создать решение с использованием модуля.

Вот то, что я пробовал до сих пор. Мне интересно, должна ли моя переменная быть инициализирована чем-то отличным от 0, или я обновляюсь в неправильной части блока кода.

class Solution {
public:

    int coinChange(vector<int>& coins, int amount) {

        int pieces = 0;
        int remainder = 0;

        for(int i = coins.size()-1; i = 0; i--) {
            if (amount % coins[i] == 0)
            {
                pieces += amount/coins[i];
            } else {
                pieces += amount/coins[i];
                remainder = amount%coins[i];
                amount = remainder;
            }
        }
        return pieces;
    }
}

Я ожидаю вывод, как указано выше. Застрял и не уверен, что еще попытаться заставить это работать.

Answer 1

Я понимаю, что вы пытаетесь сделать, но ваш код на самом деле не будет выполнять то, что вы думаете, он будет. Вот код вашего кода:

int coinChange(vector<int>& coins, int amount) {

    // Minimum number of coins to sum to 'amount'
    int pieces = 0;
    int remainder = 0;

    // Assuming 'coins' is a non-decreasing vector of ints,
    // iterate over all coins, starting from the larger ones,
    // ending with the smaller ones. This makes sense, as it
    // will use more coins of higher value, implying less
    // coins being used
    for(int i = coins.size()-1; i = 0; i--) {
        // If what's left of the original amount is
        // a multiple of the current coin, 'coins[i]',
        if (amount % coins[i] == 0)
        {
            // Increase the number of pieces by the number
            // of current coins that would satisfy it
            pieces += amount/coins[i];

            // ERROR: Why are you not updating the remaining amount?
        } else {
            // What's left of the original amount is NOT
            // a multiple of the current coin, so account
            // for as much as you can, and leave the remainder
            pieces += amount/coins[i];
            remainder = amount%coins[i];
            amount = remainder;
        }
    }

    // ERROR: What if amount != 0? Should return -1
    return pieces;
}

Если вы исправите ERROR s, о которых я упоминал выше, функция сработает, ПОЧЕМУ все целые числа в coins ведут себя следующим образом:

1. Если монета s меньше другой монеты l, то l должно быть кратно s.
2. Каждая монета должна быть> = 1.

Доказательство 1:

Если монета s меньше другой монеты, l, но l не являетсякратное s, использование l в качестве одной из монет в вашем решении может быть плохой идеей. Давайте рассмотрим пример, где coins = [4, 7] и amount = 8. Вы будете перебирать coins в порядке возрастания, начиная с 7. 7 вписывается в 8, так что вы скажете, что pieces = 1, а amount = 1 остается. Теперь 4 не вписывается в amount, поэтому вы не добавляете его. Теперь цикл for закончен, amount != 0, поэтому вы не можете выполнить функцию. Однако рабочим решением было бы две монеты 4, поэтому возвращалось бы pieces = 2.

Доказательство 2:

Если монета, c<1, может быть 0 или меньше. Если <code>c равно 0, вы разделите на 0 и выдадите ошибку. Еще более запутанно, если вы изменили свой код, вы можете добавить бесконечное количество монет на сумму 0.

Если c отрицательно, вы поделите на отрицательное, что приведет к отрицательному количеству, нарушая вашу логику.