Untitled
unknown
java
3 years ago
1.4 kB
5
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...