题解 | 跳台阶扩展问题

解题思路：

自上而下地将大问题分解为规模更小但性质相同的小问题，对于第i个台阶，它可以从i-1跳上来，也可以从i-2跳上来，...，直到从第0个台阶跳上来。

例如dfs(4)：

dfs(3)=dfs(2)+dfs(1)+dfs(0)
dfs(2)=dfs(1)+dfs(0)
dfs(1)=dfs(0)=1

因此我们可以采用递归的方法解决这个问题。

定义dfs(i)表示跳到第i个台阶的总跳法，边界就是当i=0时，调到第0个台阶的总跳法为1。

#include <iostream>
using namespace std;
int n;
int dfs(int i)
{
    if (i == 0) return 1;
    int res = 0;
    for (int j = 0; j < i; j++)
        res += dfs(j);
    return res;
}

int main()
{
    cin >> n;
    cout << dfs(n) << endl;
    return 0;
}