第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;
}
};