CoinChange

    
    // This uses bottom up dynamic progrmmaing
    // mostly return number of coins and we can get the full list too
    // Much better Time complexity O(coins.Length * amount)
    //Can use this if output format is not specifically mentioned
    public int CoinChange(int[] coins, int amount) {
     
      
        int[] dp = new int[amount+1];
        
        var dict = new Dictionary<int,int>();
        
        Array.Fill(dp,amount+1,1,amount);
        
        for(int i =0; i<coins.Length; i++){
            
            for(int j =coins[i] ; j<=amount; j++){
                
                dp[j] = Math.Min(dp[j], dp[j-coins[i]]+1);
                
                // forming the list
                if(dict.ContainsKey(j) && dp[j] <dict[j] ){
                    dict[j] =dp[j];
                   
                }
                else{
                    dict.Add(j,dp[j]);
                   
                }
                  
                 
                
            }
            
        }
        
        //Console.WriteLine(dict[amount]);
        //we have the full list in the dict, below statement will print the number of coins used for amount ,say 135
        
        
        Console.WriteLine("Number of coins for amount = "+dp[amount]);
        
        return dp[amount];
        
    }