Leetcode—— 面试题 08.01. 三步问题

本文主要是介绍Leetcode—— 面试题 08.01. 三步问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

面试题 08.01. 三步问题

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3 
 输出：4
 说明: 有四种走法
示例2:

 输入：n = 5
 输出：13
提示:

n范围在[1, 1000000]之间

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/three-steps-problem-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1.确定状态

• dp[i] 为i层台阶所爬上去的方法。

2.转移方程

• 

3.边界情况

• 初始化为0，长度为 n+1
• dp[1] = 1
• dp[2] = 2
• dp[3] = 4

程序代码(Python):

class Solution:def waysToStep(self, n: int) -> int:dp = [0 for _ in range(n+1)]dp[1] = 1if n < 2:return dp[n]dp[2] = 2if n < 3:return dp[n]dp[3] = 4for i in range(4,n+1):dp[i] = (dp[i-3] + dp[i-2] +dp[i-1]) % 1000000007return dp[n]
n = 5
s = Solution()
print(s.waysToStep(n))

程序代码(c++):

注意：两数相加再取模——(m + n) % p = (m%p + n%p) %p

class Solution {
public:int waysToStep(int n) {vector<int> dp(n+1);if(n==1)return 1;if(n==2)return 2;if(n==3)return 4;dp[1]=1; dp[2]=2; dp[3]=4;for(int i=4;i<=n;i++)dp[i] = (dp[i-1]+dp[i-2]+dp[i-3]) % 1000000007;return dp[n];}
};

 

这篇关于Leetcode—— 面试题 08.01. 三步问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---