外贸式响应式网站,网站建设技术交流,wordpress插件的选择,注册国际贸易公司需要多少钱Description
假如有n个台阶#xff0c;一次只能上1个台阶或2个台阶#xff0c;请问走到第n个台阶有几种走法#xff1f;为便于读者理解题意#xff0c;这里举例说明如下#xff1a;假如有3个台阶#xff0c;那么总计就有3种走法#xff1a;第一种为每次上1个台阶#…Description
假如有n个台阶一次只能上1个台阶或2个台阶请问走到第n个台阶有几种走法为便于读者理解题意这里举例说明如下假如有3个台阶那么总计就有3种走法第一种为每次上1个台阶上3次第二种为先上2个台阶再上1个台阶第三种为先上1个台阶再上2个台阶。输入为n输出为走到第n个台阶有几种走法
Input
比如输入是3
Output
如果输入是3走到第3个台阶的走法总计有3种1,1,1 和 1,2 和2,1输出为3
Sample Input 1
1
Sample Output 1
1
Sample Input 2
3
Sample Output 2
3
Sample Input 3
4
Sample Output 3
5
code
方法一递归适用于数据范围比较小的题
#include bits/stdc.h
using namespace std;
typedef long long LL;
typedef pairint, int PII;
const int N 1e5 10;
int a[N];
int n, res;void jump(int k) {if (k n) {res ;} else if (k n) {jump(k 1);jump(k 2);}
}void solve() {cin n;jump(0);cout res \n;
}int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int _ 1;// cin _;while (_ -- ) {solve();}return 0;
}
方法二用数组计算适用于数据量稍大的题目
#include bits/stdc.h
using namespace std;
typedef long long LL;
typedef pairint, int PII;
const int N 1e5 10;
int a[N];
int n, res;void solve() {a[1] 1;a[2] 2;for (int i 3; i 15; i ) {a[i] a[i - 1] a[i - 2];}cin n;cout a[n] \n;
}int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int _ 1;
// cin _;while (_ -- ) {solve();}return 0;
}
