有n階樓梯，每次走一步或者兩步，問有幾種走法到第n階

最近面試 的時候遇到的，記個筆記。

/**
 * 斐波那契數列
 * //0 1 1 2 3 5 8 13 21 34
 * f(n) = f(n-2)+f(n-1)
 */
public class Fibonaccisequence {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("請輸入有幾階樓梯:");
        short i = scanner.nextShort();
        Fibonaccisequence fibonaccisequence = new Fibonaccisequence();
        Short kinds = fibonaccisequence.kinds((short) i);

        System.out.println("一共有"+kinds+"種走法");

    }
    
    private Short kinds(short i){
        //f(n)=f(n-1)+f(n-2)
        //将斐波那列數放入一個有序連結清單中
        List<Short> list = new ArrayList<Short>();
        int m;
        if (list.isEmpty()){
            list.add((short) 0);
            list.add((short) 1);
        }
        //從下标等于2開始循環
        for ( m = 2 ;m<=i+1;m++){
            list.add( (short) (list.get(m - 2) + list.get(m - 1)));
        }
        return list.get(m-1);
    }
}
           

運作結果：

Connected to the target VM, address: '127.0.0.1:63097', transport: 'socket'
請輸入有幾階樓梯:
4
一共有5種走法