class Solution { //Q21 public int change(int amount, int[] coins) { int n = coins.length; // return solve(coins , n-1 , amount , new Integer[n][amount+1]); //tabulization -> n*amt | sc- n*amt int dp[][] = new int[n][amount+1]; for(int i = 0 ;i < n ; i++){ for(int j =0 ; j < amount+1 ; j++){ if(i == 0){ if(j%coins[i] == 0) dp[i][j] = 1; else dp[i][j] = 0; } else{ int notake = dp[i-1][j]; int take = 0; if(j - coins[i] >= 0) take = dp[i][j-coins[i]]; dp[i][j] = take + notake; } } } return dp[n-1][amount]; } /* by trying each coin on amount multiple times we get combonition as no coin gets repeated by trying all coins on amount multiple times we get permutation as coins gets repeated */ //Recursion-> exponential(can't determine no. of options) | //Memoization -> n*amt Sc-> n*amt + amt(stack height) public int solve(int coins[] , int i ,int amt , Integer[][] dp){ if(i == 0){ if(amt % coins[i] == 0) return 1; else return 0; } if(dp[i][amt] != null) return dp[i][amt]; //faith calls for all ways if we take or not take from next level int notake = solve(coins , i-1 , amt , dp); int take = 0; if(amt - coins[i] >= 0) take = solve(coins , i , amt - coins[i] ,dp); return dp[i][amt] = take + notake; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter