所有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英寸的一种方式)。

这个递归公式看起来眼熟吗?你能比简单递归解更好地解它吗?

---

剧透:

<子><一口><子>斐波那契序列

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)

如果你想提高这样一个算法的效率，你可以考虑使用记忆

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.

这似乎与维基百科对斐波那契数"在数学中的应用"的描述直接相关，例如，计算"1和2s的组合之和为给定总n的个数"(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<n; i++ )
            {
            int at = first;
            first = second;
            second = at + second;
            }
        return second;
        }
    public static void Main (String[] args)
        {
        Console.WriteLine (NumberOfWays (3));
        }
    }

Answer 6

c++代码运行正常

   static int numberOfWays(int n)
   {
      if (n == 1) return 1;
      else if (n == 2) return 2;
      else
      {
        static std::unordered_map<int,int> m;
        auto i = m.find(n);
        if (i != m.end())
           return i->second;
        int x = numberOfWays(n - 1) + numberOfWays(n - 2);
        m[n] = x;
        return x;
      }
   }