class Solution { //Q-20 public int coinChange(int[] coins, int amount) { int n = coins.length; if(amount == 0) return 0; // int ans = solve(coins ,n-1 , amount , new Integer[n][amount+1]); // return ans >= (int)1e9 ? -1 : ans; //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++){ //base case if(i == 0){ if(j%coins[i] == 0) dp[i][j] = j/coins[i]; else dp[i][j] = (int) 1e9; } //recursion logic else{ int notake = 0 + dp[i-1][j]; int take = (int) 1e9; if(j - coins[i] >= 0) take = 1 + dp[i][j-coins[i]]; dp[i][j] = Math.min(take , notake); } } } //if >= 1e9 , return -1 return dp[n-1][amount] >= (int)1e9 ? -1 : dp[n-1][amount]; } /* in any question where it is mentioned infinite supply or multiple use , one of the recursion calls will not reduce index , as we have to check it again and again till its invalid */ //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 amt/coins[i]; else return (int) 1e9; } if(dp[i][amt] != null) return dp[i][amt]; int notake = 0 + solve(coins , i-1 , amt , dp); int take = (int) 1e9; if(amt - coins[i] >= 0) take = 1 + solve(coins , i , amt - coins[i] ,dp); return dp[i][amt] = Math.min(take , notake); } }