Coin Change Problem: Dynamic Programming

package com.hackerrank.problems;

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class CoinChange {

    static long getWays(long n, long[] c){

        // Complete this function

        Map<String,Long> m =  new HashMap<>();

        

        return change(n, c, 0, m);

    }

    

    static long change(long n, long[] c, int index, Map<String, Long> map){

        

        if(n == 0){

            return 1;

        }

        

        if(index >= c.length){

            return 0;

        }

        

        long ways = 0;

        

        long amountWithCoin = 0;

        

        String key = n + "-" + index; 

        System.out.println("Key" + key);

        

        if(map.containsKey(key)){

            return map.get(key);

        }

        

      

        while(amountWithCoin <= n){

            long remaining = n - amountWithCoin;

            ways = ways + change(remaining, c,index+1,map);

            amountWithCoin = amountWithCoin + c[index];

            System.out.println("Amount With Coin" + amountWithCoin);

        }

        map.put(key, ways);

        return ways;

    }

    public static void main(String[] args) {

        

        int n = 35;

        

        long[] c = {2, 5, 3, 6};

        

        long ways = getWays(n, c);

        

        System.out.println(ways);

    }

}