class Solution {
public:
int f(int index,int target,vector<int>& coins,vector<vector<int>> dp) {
    if(target==0) return 1;
    if(index==0 ) {
        if(target%coins[0]==0) return 1;//target/coins[0];
        return 0;
    }
    if(dp[index][target]!=-1) return dp[index][target];
    int pick = (target-coins[index]>=0)?f(index,target-coins[index],coins,dp):0;
    int npick = f(index-1,target,coins,dp);
    return  dp[index][target]=pick+npick;
}
    int change(int amount, vector<int>& coins) {
        vector<vector<int>>dp(coins.size()+1,vector<int>(amount+1,-1));
        return f(coins.size()-1,amount,coins,dp);
    }
};