牛客网 DP3跳台阶扩展问题

在原始跳台阶问题上，我们知道只走1，2阶台阶的话，可以推出来斐波那契数列的形式进行计算操作。但是，在这里就是1，2，3，...n阶台阶了。其实思路是一样的。

在原始台阶问题，我们的状态方程是：f(n)=f(n-1)+f(n-2)的，这里解释为选择走一阶台阶，那么剩下有f(n-1)种走法，走2阶台阶，有f(n-2)种走法；同理，走3阶台阶，剩下f(n-3)种走法......

以此类推之后，我们得出了：f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(1)+f(0).的状态方程，这样我们就可以解出来了。

注意：其实状态方程列出来之后，是一个递归的过程，我们需要知道这是怎么计算出来的，那么，n=0,1时都是一种解法，n=2时就是2种解法了，而到了n=3的时候就是f(3)=f(2)+f(1)+f(0)了，这个时候f(3)就是4了。以此类推我们可以发现，f(n)=2^(n-1)，这样我们就可以放心递归了，或者你直接用这个式子计算返回值就行。

上代码：

#include <iostream>
#include<cmath>
#define MAX 100
using namespace std;
typedef long long LL;LL sum(int n){if(n==0)return 1;else if(n==1)return 1;else if(n==2)return 2;elsereturn 2*sum(n-1);}
int main() {int n;cin>>n;cout<<sum(n)<<endl;
}