Exchange Coins TLE

#1

I’m not sure how to implement a DP on my recursive algorithm as I keep getting a TLE.
Here’s my code - https://ide.codingblocks.com/s/244326

#2

Use HashMap instead of array

#3

import java.util.HashMap;
import java.util.Scanner;

public class Main {
static HashMap<Integer, Long> map = new HashMap<Integer, Long>();

public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	map.put(0, 0l);
	System.out.println(coins(n));

}

public static long coins(int n) {
	if (n == 0) {
		return 0;
	}

	if (map.containsKey(n)) {
		return map.get(n);
	}

	map.put(n, Math.max(n, coins(n / 2) + coins(n / 3) + coins(n / 4)));
	return map.get(n);

}

}

1 Like
#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.