Untitled
unknown
java
3 years ago
1.4 kB
4
Indexable
import java.util.*; class Main { public static void main(String[] args) { System.out.println("Hello, World!"); Scanner in = new Scanner(System.in); int N = in.nextInt(); int M = in.nextInt(); Map<Integer, Map<Integer, Integer>> memory = new HashMap<>(); System.out.println(dfs(N, M, memory, 10)); } public static int dfs(int N, int M, Map<Integer, Map<Integer, Integer>> memory, int denomination) { if(memory.containsKey(N) && memory.get(N).get(M) != null) return memory.get(N).get(M); if(N == 0 && M == 0) return 1; if(N == 0 || M < 10) { memory.computeIfAbsent(N, k -> new HashMap<Integer, Integer>()).put(M, 0); return 0; } int res = 0; switch(denomination) { case 10: res += dfs(N-1, M-10, memory, 10); res += dfs(N-1, M-30, memory, 30); res += dfs(N-1, M-50, memory, 50); break; case 30: res += dfs(N-1, M-30, memory, 30); res += dfs(N-1, M-50, memory, 50); break; case 50: res += dfs(N-1, M-50, memory, 50); break; } memory.computeIfAbsent(N, k -> new HashMap<Integer, Integer>()).put(M, res); return res; } }
Editor is loading...