You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer
Example 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+1
Example 2:

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

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

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<int>> memo(coins.size(),vector<int>(amount+1,0));
        sort(coins.begin(),coins.end());
        int row=coins.size();
        if(row==0 && amount==0){
            return 1;
        }

        if(row==0 && amount>0){
            return 0;
        }
        int column=amount+1;
        
        assert(coins[0]>0);
        //init 
        if(coins[0]==1) {
            for (int j = 0; j < memo[0].size(); j++) {
                memo[0][j] = 1;
            }
        } else{
            for(int j=0;j<memo[0].size();j++){
                if(j%coins[0]==0){
                    memo[0][j]=1;
                } else{
                    memo[0][j]=0;
                }
            }
        }
        
        

        for(int i=1;i<coins.size();i++){
            for(int j=0;j<amount+1;j++){
                int k=0;
                while(j-coins[i]*k>=0){
                    memo[i][j]+=memo[i-1][j-coins[i]*k];
                    k++;
                }
            }
        }

        return memo[row-1][amount];

    }
};

int main(){
    int amount=0;
    int coins[]={};

    vector<int> vec(coins,coins+sizeof(coins)/sizeof(int));
    cout<<Solution().change(amount,vec)<<endl;
    return 0;
}