跳台阶相关题目
1
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
这个和斐波那契很像,但要注意,初始的i不同,这个是 1,1,2,3,5,……
class Solution {
public:
int jumpFloor(int number) {
if (number<=2)return number;
//int a0 = 0;
int a1 = 1;
int a2 = 2;
int a3 = a1+a2;
for (int i=3;i<=number;i++)
{
a3 = a2+a1;
//a2 = a3;
a1 = a2;
a2 = a3;
}
return a3;
}
};
2 变态跳
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
3 快手笔试,魔法深渊, 一次可以跳 2的幂次
动态规划,比如 dp[3] = dp[3-2] + dp[3-1]
注意 dp[0] = 1;
参考:https://blog.****.net/jxq0816/article/details/83934641
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<long long>dp(10005,0);
int mb[10]={1,2,4,8,16,32,64,128,256,512};
dp[0] = 1;
for (int i=1;i<=1000;i++)
{
for (int j=9;j>=0;j--)
{
if (i>=mb[j])
{
dp[i] += dp[i-mb[j]];
dp[i] %= 1000000003;
}
}
}
for (int i=0;i<n;i++)
{
int t;
cin>>t;
cout<<dp[t]<<endl;
}
return 0;
}