青蛙跳
题目描述：
给出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;
}
在这里插入图片描述
