DP #518 Coin Change II

class Solution {
    public int change(int amount, int[] coins) {
        int n=coins.length;
        // int[][] dp=new int[n][amount+1];
        // for(int[] i: dp) Arrays.fill(i,-1);
        // return recur(n-1,amount,coins,dp); 
        return tabOpt(n,amount,coins);
    }

    // Space optimised Tabulation solution
    int tabOpt(int n, int a, int[] c){
        int[] dp =new int[a+1];
        for(int i=0;i<=a;i++) dp[i] = (i%c[0] ==0)?1:0;

        for(int i=1;i<n;i++){
            int[] cur = new int[a+1];
            cur[0]=1;
            for(int j=1;j<=a;j++){
                int tk = (j-c[i] >=0)?cur[j-c[i]]:0;
                int ntk = dp[j];
                cur[j] = tk+ntk;
            }
            dp=cur;
        }
        return dp[a];
    }

    // Tabulation solution
    int tab(int n, int a, int[] c){
        int[][] dp =new int[n][a+1];
        for(int i=0;i<=a;i++) dp[0][i] = (i%c[0] ==0)?1:0;
        for(int i=1;i<n;i++) dp[i][0] = 1;
        for(int i=1;i<n;i++){
            for(int j=1;j<=a;j++){
                int tk = (j-c[i] >=0)?dp[i][j-c[i]]:0;
                int ntk = dp[i-1][j];
                dp[i][j] = tk+ntk;
            }
        }
        return dp[n-1][a];
    }

    // Recursive solution
    int recur(int n, int a, int[] c,int[][] dp){
        if(a<0) return 0;
        if(n==0) return dp[n][a] = (a%c[n]==0)? 1:0;
        if(a==0) return dp[n][a] = 1;
        if(dp[n][a]!=-1) return dp[n][a];
        int tk = recur(n,a-c[n],c,dp);
        int ntk = recur(n-1,a,c,dp);
        return dp[n][a] = tk+ntk;
    }
}