1 + 2的所有组合，加上n

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

青蛙只向前移动，但它可以步长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英寸的方法）。

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

---

扰流板：

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

Answer 2

这是一个应该工作的简单伪代码实现：

 var results = [] function plan(previous, n){ if (n==0) { results.push(previous) } else if (n > 0){ plan(previous + ' step', n-1) plan(previous + ' hop', n-2) } } plan('', 5) 

如果你想提高像这样的算法的效率，你可以考虑使用memoization

Answer 3

这是一种组合方式：将n视为1 + 1 + 1 ... = n 。 现在将1对成对，逐渐增加成束1的数量，总结排列它们的可能性。

例如，将5视为1 1 1 1 1 ：

 one bunch => (1) (1) (1) (11) => 4 choose 1 possibilities to arrange one 2 with three 1's two bunches => (1) (11) (11) => 3 choose 2 possibilities to arrange two 2's with one 1 etc. 

这似乎与维基百科对斐波那契数字“数学中的使用”的描述直接相关，例如，计算“总和为给定总数n的1和2的成分数”（ http://en.wikipedia.org/ wiki / Fibonacci_number ）。

Answer 4

这个逻辑运行正常。 （递归）

 public static int numberOfWays(int n) { if (n== 1) { return 1; // step } else if (n== 2) { return 2; // (step + step) or jump } else { return numberOfWays(n- 1) + numberOfWays(n- 2); } } 

Answer 5

接受的答案未通过较大集的性能测试。 这是一个带有for循环的版本，可以满足testdome的性能测试。

 using System; public class Frog { public static int NumberOfWays (int n) { int first = 0, second = 1; for ( int i = 0; i