爬樓梯

第i階時具有某種遞推關系

精确定義

dpi 到達第i階具有的方法，dp0是沒有一階，dp1是第1階

轉移

- - - -  dpi =dp i-1  +dpi-2

初始化

dp0 =0 dp1=1

優化空間

dpi=dpi1+dpi2

dpi2=dpi1

dpi1=dpi

class Solution {
public:
    int climbStairs(int n) {
        if(n==1)return 1;
        if(n==2)return 2;
        int dpi2=1,dpi1=2;
        for(int i=3;i<=n;i++){
            int dpi=dpi1+dpi2;
            dpi2=dpi1;
            dpi1=dpi;
        }
        return dpi1;
    }   
};