算法4 爬梯子Climbing Stairs

题目：你准备要爬楼梯。你面对的是一个 n 步可以走上去的楼梯。你每次可以走一步或者两步，那么你有几种不同的方式可以爬上去吗？（n为正）

思路 ：我看到题的第一个想法，拿个数试下找规律，我以n为3来找，即要爬一个3阶楼梯，第一种一步三次，第二种先一步后两步，第三种先两步后一步，共三种，当n为4时有5种，发现到最后一次时要不就是一步要不就两步。
3阶的要不是从一阶走两步上去，要不就是从二阶走一步上去。
4阶要不是从3阶一步上去，要不就是从二阶两步上去。
即4阶的方法数 = 3阶的方法数+2阶的方法数

public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    int first = 1;
    int second = 2;
    int third=0;//n阶方法数
    for (int i = 3; i <= n; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return third;
}