Interestingly, there is a simple solution to this problem. You can use recursion:
public static int countPossibilities(int n) {
if (n == 1 || n == 2) return n;
return countPossibilities(n - 1) + countPossibilities(n - 2);
}
Whenever you're faced with this type of "tricky" problem, bear in mind that the solution is often times quite elegant, and always check to see if something can be done with recursion.
EDIT: I was assuming that you would deal with relatively small n
values in this problem, but if you deal with large ones then the method above will probably take a good amount of time to finish. One solution would be to use a Map
that would map n
to countPossibilities(n)
- this way, there would be no time wasted doing a computation that you've already done. Something like this:
private static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
static {
map.put(1, 1);
map.put(2, 2);
}
public static int countPossibilities(int n) {
if (map.containsKey(n))
return map.get(n);
int a, b;
if (map.containsKey(n - 1))
a = map.get(n - 1);
else {
a = countPossibilities(n - 1);
map.put(n - 1, a);
}
if (map.containsKey(n - 2))
b = map.get(n - 2);
else {
b = countPossibilities(n - 2);
map.put(n - 2, b);
}
return a + b;
}
Try this with n = 1000
. The second method is literally orders of magnitude faster than the first one.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…