台阶问题递归优化

131 阅读 0 评论 87 点赞

我是靠谱客的博主单薄滑板，这篇文章主要介绍台阶问题递归优化，现在分享给大家，希望可以做个参考。

写了母牛生小牛问题的算法，发现递归算法可以用迭代来优化！

下面给出台阶问题的优化：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
【问题描述】
爬楼梯看似简单但Dadou小朋友玩的不亦乐乎，Dadou小朋友可以一步上一阶，可以一步上两阶，也可以一步上三阶，短短的9阶台阶Dadou 小朋友就找到了149种不同的上法，
Dadou小朋友除了爱运动之外还喜欢数学，对不同的台阶数的楼梯有多少中上法很是好奇。。。。
【问题输入】
一个整数n 表示该楼梯的台阶数
（1<=n>=10^6）
【问题输出】
一个整数m，m为n阶台阶一共有多少种上法由于m过于大所以要求输出m对1000007取余的结果
【样例1】
输入：3
输出： 4
【样例2】
输入：9
输出： 149*/
public class TaiJie3 {
public static int sum(int n) {
int t1 = 1, t2 = 2, t3 = 4, tn = 0;
if (n == 1)
return 1;
else if (n == 2)
return 2;
else if (n == 3)
return 4;
else {
for (int i = 4; i <= n; i++) {
tn = t3 + t2 + t1;
t1 = t2;
t2 = t3;
t3 = tn;
}
return tn;
}
}
public static void main(String args[]) {
System.out.println(sum(39));
}
}

同样，200多台阶还会溢出，这个怎么处理？后期还会更新

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*如果从1楼走到10楼，每层有两段楼梯，每段有9-12层台阶（可随机生成），
* 段与段之间有转向平台，每个转向平台需要走1大步一小步，或者3小步，
* 请问从一楼到十楼每步走1-2个台阶共有多少种走法*/
//很明显此题不用考虑左右脚的问题，那n==1时return1；n==2时return2；
public class TaiJiePRO {
public static long sum(int n) {
int t1 = 1, t2 = 2, tn = 0;
for (int i = 3; i <= n; i++) {
tn = t1 + t2;
t1 = t2;
t2 = tn;
}
return tn;
}
public static void main(String args[]) {
int n = 9 * 3;
for (int i = 0; i < 18; i++) {
int step = (int) (Math.random() * 4 + 9);
n = n + step;
}
System.out.println(sum(n));
}
}