计算和显示爬楼梯java的方法

Question

我写了一些代码来计算,并且还打印了通过n步骤爬上给定楼梯的方法.

一次只能爬1或2个楼梯.我知道这是一个已知的面试问题,我写了一些代码与你分享.

问题是我错过了很多序列.能否请您查看并帮助我了解我缺少的逻辑？谢谢你的帮助

我的代码:

/**
 * 
 */
package prep;

/**
 * @author rohandalvi
 *
 */
public class generateAllPermutations {

    /**
     * @param args
     */
    static int totalCounter = 0;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int numberOfStairs = 10;
        int countSoFar = 0;
        String path = "";
        for(int i=1;i<3;i++){
            path = ""+i;
            displayAllPerms(numberOfStairs, i, path);
        }
        System.out.println("Total combinations found "+totalCounter);
    }

    public static void displayAllPerms(int n,int countSoFar,String s){
        if(countSoFar > n) return;
        else if(countSoFar < n){
            for(int i=1;i<3;i++){
                s+=" "+i;
                countSoFar+=i;
                displayAllPerms(n, countSoFar, s);
            }
        }else{
            System.out.println("Found combination "+s);
            totalCounter++;
            return;
        }
    }

}

结果:

Found combination 1 1 1 1 1 1 1 1 1 1
Found combination 1 1 1 1 1 1 1 1 2
Found combination 1 1 1 1 1 1 1 2 1
Found combination 1 1 1 1 1 1 2 1 1
Found combination 1 1 1 1 1 2 1 1 1
Found combination 1 1 1 1 1 2 1 2
Found combination 1 1 1 1 2 1 1 1 1
Found combination 1 1 1 1 2 1 1 2
Found combination 1 1 1 1 2 1 2 1
Found combination 1 1 1 2 1 1 1 1 1
Found combination 1 1 1 2 1 1 1 2
Found combination 1 1 1 2 1 1 2 1
Found combination 1 1 1 2 1 2 1 1
Found combination 1 1 2 1 1 1 1 1 1
Found combination 1 1 2 1 1 1 1 2
Found combination 1 1 2 1 1 1 2 1
Found combination 1 1 2 1 1 2 1 1
Found combination 1 1 2 1 2 1 1 1
Found combination 1 1 2 1 2 1 2
Found combination 2 1 1 1 1 1 1 1 1
Found combination 2 1 1 1 1 1 1 2
Found combination 2 1 1 1 1 1 2 1
Found combination 2 1 1 1 1 2 1 1
Found combination 2 1 1 1 2 1 1 1
Found combination 2 1 1 1 2 1 2
Found combination 2 1 1 2 1 1 1 1
Found combination 2 1 1 2 1 1 2
Found combination 2 1 1 2 1 2 1
Found combination 2 1 2 1 1 1 1 1
Found combination 2 1 2 1 1 1 2
Found combination 2 1 2 1 1 2 1
Found combination 2 1 2 1 2 1 1

基本上,我缺少像这样的组合:

2 2 2 2 2

还有更多的组合,基本上都以2 2开头

Answer 1

让我首先说明这个问题的递归方法,我怀疑你已经采取了.然后,我将继续讨论代码.

爬3步的方法= [爬2步的方法] + [爬1步的方法].

概括,攀登n步骤的方法= [攀爬n-1步骤的方法] + [攀爬n-2步骤的方法].

如果您有没有注意到,这是斐波那契模式(可替代的解决方案是简单地返回n+1^次 Fibonacci数;!试试吧).

public int getWays(int n) {
    if(n <= 1) return n;

    int result = 0;
    for (int i = 1; (i <= 2 && i <= n); i++)
        result += getWays(n-i);
    return result;
}

// Usage:
int steps = 4;
getWays(steps + 1);    // 5 ways

现在,如果你想看看所采取的组合.我采取的方法略有不同,我认为更直观.

public static void waysToReachN(int currentValue, int n, List<Integer> pathSoFar) {
    if(currentValue == n) {
        System.out.println(pathSoFar);
        return;
    } else if(currentValue > n) {
        return;
    }
    for(int i = 1 ; i <= 2 ; i++) {
        // add step
        pathSoFar.add(i);

        // recurse
        waysToReachN(currentValue + i, n, pathSoFar);

        // remove step
        pathSoFar.remove(pathSoFar.size()-1);
    }
}

// Usage:
int currentValue = 0, n = 4;
waysToReachN(currentValue, n, new ArrayList<Integer());

所以,我们发现有5种方法可以攀爬4个楼梯.方式是,

[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]

如果不清楚,请告诉我.