如何添加递归函数

Question

我很困惑如何用JAVA写这个：有一个有N个台阶的楼梯，你可以一次爬上1或2个台阶。给定 N，编写一个函数，返回您可以爬楼梯的独特方式的数量。步骤的顺序很重要。例如，如果 N 为 4，则有 5 种独特的方式：1, 1, 1, 12, 1, 11, 2, 11, 1, 22, 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) {

    if (n == 0) {

        return 1;

    }

    int sum = 0;

    for(Integer x: numbers) {

        if (x <= n) {

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

        }

    }

    return sum;

}

您不必担心n是否为负数，因为您不会在可能发生的情况下进行递归调用。（当然，您也应该注意n原始调用中的否定。）