AcWing 821. 跳台阶
原题链接
困难
作者:
STU756
,
2021-01-20 17:19:50
,
所有人可见
,
阅读 293
//c++
#include <iostream>
using namespace std;
//动态规划
//f(n)表示走n级台阶的总方案数,一步和两步有两种到达第n级阶梯的方案,分别为f(n-1),f(n-2),那么
//f(n) = f(n-1) + f(n-2),反过来递推即可
//Time:O(N), Space:O(1)
int main(){
int n;
cin >> n;
int f1 = 1, f2 = 1 + 1;
for(int i = 3; i <= n; i++) {
int tmp = f2;
f2 += f1;
f1 = tmp;
}
if(n == 1) cout << f1 << endl;
else cout << f2 << endl;
return 0;
}
//递归
#include <iostream>
using namespace std;
//递归Time:O(N!) Space:O(1)
int f(int n) {
if(n == 1) return 1;
else if(n == 2) return 2;
return f(n - 1) + f(n - 2);
}
//递归+打表Time:O(N) Space:O(N)
int a[16];// 1 <= n <= 15
int f2(int n ) {
if(a[n]) return a[n];
return f2(n - 1) + f2(n - 2);
}
int main(){
int n;
cin >>n;
a[1] = 1, a[2] = 2;
cout << f2(n) << endl;
return 0;
}
//==================================================================================
//java
import java.util.Scanner;
public class Main{
public static void main(String...args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
if(n < 1 || n > 15) throw new IllegalArgumentException("输入参数错误。");
int f2 = 2, f1 = 1;
for(int i = 3; i <= n; i++) {
int tmp = f2;
f2 += f1;
f1 = tmp;
}
if(n == 1) System.out.println(f1);
else System.out.println(f2);
}
}
//递归
import java.util.Scanner;
public class Main{
static int f(int n) {
if(n == 1) return 1;
else if(n == 2) return 2;
return f(n - 1) + f(n - 2);
}
//打表
static int[] a = new int[16];
static int f2(int n) {
if(a[n]!=0) return a[n];
return f2(n - 1) + f2(n - 2);
}
public static void main(String...args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
if(n < 1 || n > 15) throw new IllegalArgumentException("输入参数错误。");
// int f2 = 2, f1 = 1;
// for(int i = 3; i <= n; i++) {
// int tmp = f2;
// f2 += f1;
// f1 = tmp;
// }
// if(n == 1) System.out.println(f1);
// else System.out.println(f2);
//System.out.println(f(n));
a[1] = 1; a[2] = 2;
System.out.println(f2(n));
}
}