NO.8  跳臺階

知識點：遞歸和循環

題目描述

思路：

對于本題,前提只有 一次 1階或者2階的跳法。

a.如果兩種跳法，1階或者2階，那么假定第一次跳的是一階，那么剩下的是n-1個臺階，跳法是f(n-1);

b.假定第一次跳的是2階，那么剩下的是n-2個臺階，跳法是f(n-2)

c.由a/b假設可以得出總跳法為: f(n) = f(n-1) + f(n-2) 

d.然后通過實際的情況可以得出：只有一階的時候 f(1) = 1 ,只有兩階的時候可以有 f(2) = 2

e.可以發現最終得出的是一個斐波那契數列：

              | 1, (n=1)

f(n) =     | 2, (n=2)

代碼：

解法一：使用遞歸

public class Solution {    public int JumpFloor(int target) {        if(target==1||target==2){            return target;        }        else{            return JumpFloor(target-1)+JumpFloor(target-2);        }    }}解法二：使用迭代
public class Solution {    public int JumpFloor(int target) {        if(target==0)            return 1;        if(target==1)            return 1;        int si_1=1;        int si_2=1;        int result=0;        for(int i=2;i<=target;i++){            result=si_1+si_2;            si_2=si_1;            si_1=result;        }        return result;    }}