1 + 2的所有组合,增加到n

Question

我正在努力解决这个问题,作为编程面试的准备:

青蛙只向前移动,但它可以步长1英寸或跳跃2英寸长.青蛙可以使用不同的步骤和跳跃组合覆盖相同的距离.

编写一个函数,计算青蛙可以用来覆盖给定距离的不同组合的数量.

例如,可以通过三种方式覆盖3英寸的距离:步进步骤,步进跳跃和跳跃步骤.

我认为有一个非常简单的解决方案,但我似乎无法找到它.我想使用递归,但我看不出如何.这是我到目前为止:

public class Frog {

    static int combinations = 0;
    static int step = 1;
    static int jump = 2;
    static int[] arr = {step, jump};

    public static int numberOfWays(int n) {
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            sum += arr[i];
            System.out.println("SUM outer loop: " + sum + " : " + arr[i]);
            while (sum != 3) {
                for (int j = 0; j < arr.length; j++) {
                    if (sum + arr[j] <= 3) {
                        sum += arr[j];
                        System.out.println("SUM inner loop: " + sum + " : " + arr[j]);
                        if (sum == 3) {
                            combinations++;
                            System.out.println("Combinations " + combinations);
                        }
                    }
                }
            }
        }
        return combinations;
    }

    public static void main(String[] args) {
        System.out.println(numberOfWays(3));
    }
}

它没有找到所有组合,我认为代码非常糟糕.任何人都能很好地解决这个问题吗？

Answer 1

认为你有一个知道如何解决"小问题"问题的oracle,你只需要用较小的问题来解决问题.这是递归方法.

在你的情况下,你解决foo(n),通过分割青蛙可以在最后一步做的可能的动作,并总结它们:

foo(n) = foo(n-1) + foo(n-2)
            ^         ^
         1 step    2 steps

另外,你需要一个停止子句foo(0) = 1, foo(1)=1(单向移动0或1英寸).

这个递归公式看起来很熟悉吗？你能比天真的递归解决方案更好地解决它吗？

扰流板:

^{_{斐波那契序列}}