Вам дан целочисленный массив coins, представляющий монеты разного номинала, и целочисленный массив amount, представляющий общую сумму денег.

Возвращает количество комбинаций, составляющих эту сумму. Если эту сумму денег нельзя компенсировать ни одной комбинацией монет, верните 0.

Вы можете предположить, что у вас есть бесконечное количество монет каждого вида.

Ответ гарантировано соответствует 32-разрядному целому числу со знаком.

Пример 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1a

Пример 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Пример 3:

Input: amount = 10, coins = [10]
Output: 1
Constraints:

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000

class Solution {
public:
    // no of ways
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        vector<vector<int>> dp(n+1, vector<int> (amount+1, 0));
        for(int i=1;i<n+1;i++){
            for(int j=0;j<amount+1;j++){
                if(j==0)
                    dp[i][j]=1;
                else if(coins[i-1]<=j)
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[n][amount];
    }
};

Почему ДП? Из-за повторения!!

Наша задача состоит в том, чтобы определить, сколько различных способов мы можем восполнить эту сумму, используя монеты.

Этот вопрос не задает вам ни одного способа … будьте осторожны [1,2,2] или [2,1,2] или [2,2,1] все считаются как 1.

dp[0][1], dp[0][2], ….. dp[0][amount+1] установлен в 0, так как в то время у нас не было монет, поэтому не было возможности.

dp[0][0] установлен в 1 … это означает, что у нас нет монет и нам нужна сумма 0, поэтому есть 1 возможный способ ничего не выбрать

dp[1][0], dp[2][0]…… dp[n+1][0] — все установлены в 1, потому что есть один возможный способ ничего не выбирать.

for dp[2][4] означает, что у вас есть монеты [1,2] из массива nums, и вы должны сделать сумму =4, тогда это возможные способы…

[1,1,1,1]
[1,1,2]
[2,2]

Аналогично идем со всеми и получаем окончательный ответ в dp[n+1][amount].

Спасибо

Не стесняйтесь задавать любые вопросы или улучшать эту версию :)