View difference between Paste ID: VdEyrB4U and 2MxLbmv1
SHOW: | | - or go back to the newest paste.
1
public class Coins {
2-
	public static int[] V = new int[] {1, 3, 5};
2+
	public static int[] V;
3-
	public static int S = 11;
3+
	public static int S = 10000000;
4
	static int asdf = 0;
5
	public static void main(String[] args) {
6-
		System.out.println(recurse(2, 0));
6+
		V = new int[100];
7
		for (int i = 0; i < 100; ++i)
8
		{
9
			V[i] = i * 2 + 1;
10
		}
11
		System.out.println(recurse(V.length - 1, 0));
12
		System.out.println(asdf);
13-
		for (int j = (S - total) / V[i]; j >= 0; j--) {
13+
14
	
15
	public static int recurse(int i, int total) {
16
		int min = -1;
17
		int num = 0;
18
		if (i < 0) return (S - total == 0) ? 0 : -1;
19
		int N = (S - total) / V[i];
20
		for (int j = N; j >= 0 && j >= N - 1; j--) {
21
			int tmp = recurse(i - 1, total + V[i] * j);
22
			if (tmp >= 0 && (min == -1 || tmp < min)) {
23
				min = tmp;
24
				num = j;
25
			}
26
			++asdf;
27
		}
28
		return min + num;
29
	}
30
}