【每日算法Day 79】所有人都会做的入门题,但是能看出你的代码能力!
这两天要帮老师录制一下题解视频,所以题目挑简单一点的,减(shui)轻(liang)大(pian)家(wen)压(zhang)力。
题目链接
LeetCode 面试题 08.01. 三步问题[1]
题目描述
三步问题。有个小孩正在上楼梯,楼梯有 阶台阶,小孩一次可以上 阶、 阶或 阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模 。
示例1
输入:
n = 3
输出:
4
解释:
有四种走法
示例2
输入:
n = 5
输出:
13
题解
这道题是动态规划入门题,我相信大家都会做,如果不会做,那就当我没说过这句话。
令 为上 个台阶的方案数,那么最后一步可以是跳 步,或者跳 步,或者跳 步过去的,所以就有:
初始情况就是 。
然后利用取模的加法公式,可以每算出一个 都取一下模。
当然了这题太水了,我主要就是想看看大家会怎么实现呢?
代码
定义长度为 的数组
最朴素的方法当然是定义长度为 的数组,然后算就完事了,代码如下:
typedef long long ll;
const ll p = 1e9+7;
const int N = 1e6+10;
class Solution {
public:
ll f[N] = {1, 2, 4};
int waysToStep(int n) {
for (int i = 3; i < n; ++i) {
f[i] = (f[i-1] + f[i-2] + f[i-3]) % p;
}
return f[n-1];
}
};
定义四个变量
但是这样太费空间了啊,其实每次只需要用到之前的三个状态就行了,然后还要用个临时变量用来交换状态值,代码如下:
typedef long long ll;
const ll p = 1e9+7;
class Solution {
public:
int waysToStep(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;
ll a = 1, b = 2, c = 4, d;
for (int i = 3; i < n; ++i) {
d = (a + b + c) % p;
a = b;
b = c;
c = d;
}
return d;
}
};
定义长度为 的数组
但是用 个变量也太丑陋了,对于我这种处女座患者(对不起我是射手座)来说,完全无法忍受!
所以我直接定义了一个长度为 的数组,然后下标对 取模来实现循环数组,这样代码看起来就很舒服啦:
typedef long long ll;
const ll p = 1e9+7;
class Solution {
public:
int waysToStep(int n) {
ll f[3] = {1, 2, 4};
for (int i = 3; i < n; ++i) {
(f[i%3] += f[(i-1)%3] + f[(i-2)%3]) %= p;
}
return f[(n-1)%3];
}
};
应读者要求,再来个 python
代码:
class Solution:
def waysToStep(self, n: int) -> int:
f = [1, 2, 4]
for i in range(3, n):
f[i%3] += f[(i-1)%3] + f[(i-2)%3]
f[i%3] %= 1e9+7;
return int(f[(n-1)%3])
参考资料
[1]
LeetCode 面试题 08.01. 三步问题: https://leetcode-cn.com/problems/three-steps-problem-lcci/
算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。