DAY31：Climbing Stairs

題目地址：Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2Output: 2Explanation: There are two ways to climb to the top.1. 1 step + 1 step2. 2 steps

Example 2:

Input: 3Output: 3Explanation: There are three ways to climb to the top.1. 1 step + 1 step + 1 step2. 1 step + 2 steps3. 2 steps + 1 step

有n級樓梯，你一次可以爬一級或兩級，問爬上n級樓梯有多少種爬法？

思路：因為一次你能爬一級或兩級，所以除去最後一次，n級的爬法f(n)可以等於f(n-1)+f(n-2)。求的就是斐波那契數列。

代碼：

public class Main { public static void main(String[] args){ System.out.print(climbStair(5)); } //遞歸 public static int climbStairs(int n) { if(n == 1){ return 1; } if(n == 2){ return 2; } return climbStairs(n-1)+climbStairs(n-2); } //非遞歸 public static int climbStair(int n) { int num1 = 1; int num2 = 2; int sum = 0; if(n == 1){ return 1; } if(n == 2){ return 2; } for(int i = 2;i < n;i++){ sum = num1+num2; num1 = num2; num2 = sum; } return sum; }}

推薦閱讀：