时间戳

首页 > 解决方案 > 楼梯问题：如何打印组合？

java - 楼梯问题：如何打印组合？

问题描述

问题：

在这个问题中，我们正在评估的场景如下：你站在楼梯的底部，并且正走向顶部。小步走上一级台阶，大步走两级。您想根据大小步幅的不同组合计算爬上整个楼梯的方式的数量。例如，一个三级楼梯可以通过三种不同的方式爬上：三小步，一小步后一大步，或一大步后一小步。

调用waysToClimb(3) 应该产生以下输出：

1 1 1,
1 2,
2 1

我的代码：

public static void waysToClimb(int n){
    if(n == 0) 
        System.out.print("");
    else if(n == 1)
        System.out.print("1");
    else {
        System.out.print("1 "); 
        waysToClimb(n - 1);
        System.out.print(",");
        System.out.print("2 ");
        waysToClimb(n - 2);
    }
}

我的输出：

1 1 1,
2,
2 1

我的递归似乎不记得它采取任何想法如何解决它的路径？

编辑：

谢谢大家的回复。这么晚才回复很抱歉

我想到了

public static void waysToClimb(int n){

    String s ="[";
    int p=0;
    com(s,p,n);

}

public static void com(String s,int p,int n){

    if(n==0 && p==2)

    System.out.print(s.substring(0,s.length()-2)+"]");

    else if(n==0 && p !=0)

    System.out.print(s+"");

    else if(n==0 && p==0)

    System.out.print("");

    else if(n==1)

    System.out.print(s+"1]");

    else {

        com(s+"1, ",1,n-1);
        System.out.println();
        com(s+"2, ",2,n-2);

    }

}

标签： javadepth-first-searchbacktracking

解决方案

如果您明确想要打印所有路径（与计算它们或找到特定路径不同），则需要将它们一直存储到 0。

public static void waysToClimb(int n, List<Integer> path)
{
    if (n == 0)
    {
        //  print whole path
        for (Integer i: path)
        {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    else if (n == 1)
    {
        List<Integer> newPath = new ArrayList<Integer>(path);
        newPath.add(1);
        waysToClimb(n-1, newPath);
    }
    else if (n > 1)
    {
        List<Integer> newPath1 = new ArrayList<Integer>(path);
        newPath1.add(1);
        waysToClimb(n-1, newPath1);

        List<Integer> newPath2 = new ArrayList<Integer>(path);
        newPath2.add(2);
        waysToClimb(n-2, newPath2);
    }
}

初次通话：waysToClimb(5, new ArrayList<Integer>());

推荐阅读