题目描述：

给出n阶台阶，每次只可以前进一步或者两步，中途有一次机会可以后退一步，这次机会也可以不使用，到达最后一个台阶一共有多少种走法？

题目分析：

本题是在原本经典跳楼梯上增加了可以有一次回退的条件。

原本的题怎么做呢？

#include <iostream>
using namespace std;
const int N = 1e3+10;
int dp[N];
int main(){
    int n;
    cin>>n;
    dp[0] = 1;
    dp[1] = 1;
    for (int i=2;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    cout<<dp[n]<<endl;
    return 0;
}

但本题增加了一个条件, 在每个台阶上都有往回跳一次的机会。首先i=0和i=n不能往回跳，所以往回跳的台阶范围为[1~n-1].

假设dp是第一部分，没有算过往回退一步时候每一个阶梯所需要的步数。

i	dp
0	1
1	1
2	2
3	3
4	5
5	8
6	13

举个例子：

假设从第i个台阶回跳到i-1层。

首先i-1层就会新增dp[i]，那么i层由于i-1层增加dp[i]第i层也增加dp[i]（前进一步）。

那么i+1层新增的就是2*dp[i](i层和i-1层新增的和)。

那么第i+2层新增的就是3*dp[i](i层和i+1层新增的和)。

那么第i+3层新增的就是5*dp[i](i+1层和i+2层新增的和)。

假设i+4层为楼梯顶端，那么i+4新增的就是8*dp[i](i+2层和i+3层新增的和)，

因此台阶末端新增的就是dp[i]*dp[i+4-i+1]? = dp[i] *dp[5]。

因此通项为：

从i层回跳，那么楼梯(n层)末端新增的就是：

dp[i]*dp[n-i+1]

#include <iostream>
using namespace std;
const int N = 1e3+10;
int dp[N];
int main(){
    int n;
    cin>>n;
    dp[0] = 1;
    dp[1] = 1;
    for (int i=2;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    int res = dp[n];
    for (int i=1;i<n;i++){//回跳的范围是1~n-1
        res +=dp[i]*dp[n-i+1];
    }
    cout<<res<<endl;
    return 0;
}

喜欢的话麻烦给个赞！