如何添加递归函数

Question

我很困惑如何用JAVA写这个：有一个有N个台阶的楼梯，你可以一次爬上1或2个台阶。给定 N，编写一个函数，返回您可以爬楼梯的独特方式的数量。步骤的顺序很重要。

例如，如果 N 为 4，则有 5 种独特的方式：

1, 1, 1, 1

2, 1, 1

1, 2, 1

1, 1, 2

2, 2

如果不是一次只能爬 1 步或 2 步，而是可以从一组正整数 X 中爬上任意数字会怎样？例如，如果 X = {1, 3, 5}，您可以一次爬 1、3 或 5 步。

基本上，我可以做第一部分并理解较难部分的逻辑，答案是：f(n) = f(n-1) + f(n-3) + f(n-5)。谁能帮我？这是我的方法：

public static void main(String[] args) {

 int n = 4;

 Set < Integer > list = new HashSet < Integer > ();

 list.add(1);

 list.add(3);

 list.add(5);

 int ways = reachNFloorSet(list, n, 0);

 //     int ways = reachNFloor(n);

 System.out.println(n + " Floor is reached in " + ways + " different way/s.");

}

public static int reachNFloor(int n) { // easy part

 if (n <= 1) {

  return 1;

 }

 return reachNFloor(n - 1) + reachNFloor(n - 2);

}

public static int reachNFloorSet(Set < Integer > numbers, int n, int sum) {

 if (n < 0) {

  return 0;

 } else if (n == 0) {

  return 1;

 }

 for (Integer x: numbers) {

  if (x <= n) {

   sum += reachNFloorSet(numbers, n - x, sum);

  }

 }

 return sum;

}

我认为问题出在 for 循环上，但我无法弄清楚如何使其正确。

Answer 1

当n为负数或 0 in 时reachNFloorSet()，您将返回 0 或 1，但您应该返回sumor sum + 1。否则，您将丢弃所有积累的信息。我认为，重写您的方法会更好，这样就不必担心已经采取了多少步骤：public static int reachNFloorSet (Set<Integer> numbers, int n) {&nbsp; &nbsp; if (n == 0) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; }&nbsp; &nbsp; int sum = 0;&nbsp; &nbsp; for(Integer x: numbers) {&nbsp; &nbsp; &nbsp; &nbsp; if (x <= n) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum += reachNFloorSet(numbers, n-x);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return sum;}您不必担心n是否为负数，因为您不会在可能发生的情况下进行递归调用。（当然，您也应该注意n原始调用中的否定。）