java - 加到 n 的 1 + 2 的所有组合

Question

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

A frog only moves forward, but it can move in steps 1 inch long or in jumps 2 inches long. A frog can cover the same distance using different combinations of steps and jumps.

Write a function that calculates the number of different combinations a frog can use to cover a given distance.

For example, a distance of 3 inches can be covered in three ways: step-step-step, step-jump, and jump-step.

我认为对此有一个非常简单的解决方案，但我似乎找不到它。我想使用递归，但我不知道如何使用。这是我目前所拥有的:

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

假设你有一个知道如何解决“小问题”的神谕，你只需要用小问题来喂养它。这就是递归方法。

在你的例子中，你解决了 foo(n)，通过拆分 Frog 在最后一步可以做的可能 Action ，然后将它们相加):

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

此外，您需要一个 foo(0) = 1, foo(1)=1 的停止子句(一种移动 0 或 1 英寸的方法)。

这个递归公式是不是很眼熟？你能比朴素的递归解决方案更好地解决它吗？

---

剧透:

^{_{Fibonacci Sequence}}