题目描述
楼梯有n阶，可以一步上一阶、两阶或三阶，问有多少种不同的走法 由于答案很大，mod(1e9+7)输出
输入数据
一个正整数n，代表楼梯的阶数，n<=1000000
输出数据
方案数
样例输入
3
样例输出
4
程序分析
解题思路
第一种解法，使用递归的思想第二种解法，利用哈希算法第三者解法，使用动态规划 边界：dp[1] = 1 dp[2] = 2 dp[3] = 4 转移方程：dp[n] = dp[n-1]+dp[n-2]+dp[n-3] (n>=4) 最优子结构：比如 dp[8] = dp[7]+dp[6]+dp[5]，则dp[7]与dp[6]与dp[5]就是dp[8]的最优子结构和之模等于模之和
代码
def f(lou
):
if lou
== 1:
print(1)
return
elif lou
== 2:
print(2)
return
elif lou
== 3:
print(4)
return
else:
a
, b
, c
= 1, 2, 4
for i
in range(4, lou
+1):
a
, b
, c
= b
, c
, (a
+b
+c
)% (pow(10, 9)+7)
print(c
)
n
= int(input())
f
(n
)
import java
.util
.Scanner
;
public class Main2 {
public static long dp(int n
){
if(n
==1)
return 1L
;
if(n
==2)
return 2L
;
if(n
==3)
return 4L
;
long a
= 1L
;
long b
= 2L
;
long c
= 4L
;
long temp
= 0;
for(int i
=4;i
<=n
;i
++){
temp
= (long) ((a
+b
+c
) % (1e9+7));
a
=b
;
b
=c
;
c
=temp
;
}
return c
;
}
public static void main(String
[] args
) {
Scanner sc
=new Scanner(System
.in
);
int n
=sc
.nextInt();
System
.out
.println(dp(n
));
}
}
