递归与动态规划

规律：f(1)=1,f(2)=2,f(3)=f(2)+f(1),f(n)=f(n-1)+f(n-2)
结果完全依赖于前两阶梯方法之和
1.递归

int method(int n){
    if(n<=2){
        return n;
    }
    return method(n-1)+method(n-2);
}

2.动态规划

int method(int n){
    if(n<=2){
        return n;
    }
    int pre2=1,pre1=2;//首次执行到这里，说明n=3。先把之前两阶梯的值取出来，因为第三次依赖于前两层
    for(int i=2;i<n;i++){
        int cur=pre1+pre2;//第三层的结果
        pre2=pre1;//更新n-2层的结果，为了下一次循环
        pre1=cur;//更新n-1层的结果，为了下一次循环
    }
    return pre1;
}