青蛙跳

题目描述：

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

题目分析

最基础的青蛙跳是一组斐波那契数列， 即，： 如果不使用向后跳， 则按照斐波那契数列计算
其公式： f[i] = f[i-1] + f[i-2] 其中f[0]=1 f[1]=1
则有：
n=1; f[1]=1
n=2; f[2]=f[1]+f[0]=2
n=3; f[3]=f[2]+f[1]=3
...
n; f[n]=f[n-1] + f[n-2]
所以在这一思路下的代码为：

#include<iostream>
using namespace std;
/*利用 动态规划，这里只需要2个变量来维护。
*/
int jump_floor(int n){
    //边界条件判断
    int old1=1， old2=1;
    if (n == 1) return 1;
    int ans;
    for(int i=1; i<n; i++){
        ans = old1+old2;
        old2=old1;
        old1=ans;
    }
    return ans;
}


int main(){
    int number;
    cin >>number;
    cout<<jump_floor(number)<<endl;
    return 0;
}

样例：

在这里插入图片描述

针对青蛙跳的变式时，需要思考清楚逻辑，一般来说，这些改动都是有规律可循的*
针对本题，有如下思考：

在这里插入图片描述

给出代码如下：（需要注意， 代码中从0开始，途中i-1变为i）
其中：
f [ i ] × f [ n − i + 1 ] f[i] \times f[n-i+1]f[i]×f[n−i+1]

#include<iostream>
#include<vector>
using namespace std;
int jump_floor(int n){
    //边界条件判断
    vector<int> dp;
    for(int i=0; i<n; i++) dp.push_back(0);
    dp[0] = 1; 
    dp[1] = 2; 
    for(int i=2; i<n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    int ans;
    ans = dp[n-1]; //不使用回跳
    for(int i=0; i<n-1; i++){
        ans += (dp[i] * dp[n-i-1]);
    }
    return ans;
}


int main(){
    int number;
    cin >>number;
    cout<<jump_floor(number)<<endl;
    return 0;
}

在这里插入图片描述