|
C++ 求 楼梯有n阶，可以一步上一阶、两阶或三阶，问有多少种不同的走法，由于答案很大，mod(1e9+7)输出
基本思路
采用递归思路较为清晰，但是时间消耗较多，这里采用动态规划的思路：
根据题目条件
走一阶，有一种走法
走两阶，有两种走法
走三阶，有四种走法
由于走到某一阶，只可能是1步走到，2步走到，3步走到，因此，走到第n阶，共有：
c
o
u
n
t
[
n
]
=
c
o
u
n
t
[
n
?
1
]
+
c
o
u
n
t
[
n
?
2
]
+
c
o
u
n
t
[
n
?
3
]
count[n] = count[n-1]+count[n-2]+count[n-3]
count[n]=count[n?1]+count[n?2]+count[n?3]
种走法
因此，从4阶开始：
c
o
u
n
t
[
4
]
=
c
o
u
n
t
[
3
]
+
c
o
u
n
t
[
2
]
+
c
o
u
n
t
[
1
]
=
7
c
o
u
n
t
[
5
]
=
c
o
u
n
t
[
4
]
+
c
o
u
n
t
[
3
]
+
c
o
u
n
t
[
2
]
=
13
c
o
u
n
t
[
6
]
=
c
o
u
n
t
[
5
]
+
c
o
u
n
t
[
4
]
+
c
o
u
n
t
[
3
]
=
24
.
.
.
\begin{aligned} &count[4] = count[3]+count[2]+count[1] = 7\\ &count[5] = count[4]+count[3]+count[2] = 13\\ &count[6] = count[5]+count[4]+count[3] = 24\\ &... \end{aligned}
?count[4]=count[3]+count[2]+count[1]=7count[5]=count[4]+count[3]+count[2]=13count[6]=count[5]+count[4]+count[3]=24...?
后续的递推只需要简单的相加即可。
对于每次求和的结果，对1e9+7取模，即可满足题目要求。
直接上代码
#include<iostream>
using namespace std;
static const int mod = 1e9 + 7;
int main(){
int n;
long max[1000005];
cin >> n;
int i = 0;
max[0] = 1;
max[1] = 2;
max[2] = 4;
for (int j = 3; j < n; j++){
max[j] = (max[j - 1] + max[j - 2] + max[j - 3]) % mod;
}
cout << max[n-1]<<endl;
return 0;
}
|