动态规划攻略之：三步问题

动态规划攻略之：三步问题

题目

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

示例1：

输入：n = 3

示例2：

输入：n = 5

解题思路

根据题意，此题的思路与之前爬楼梯的问题一致。

n 层楼梯的走法可以分为3种情况：

剩余 1 层，可以走一步；剩余俩层，可以走 1+1，2 两种方式；剩余三层，可以走 1+1+1，1+2，2+1, 3 一共4中方式；

由此可以得出一个递推公式：第i层台阶可以由 i-1、i-2、i-3 层台阶相加而来，取模，故dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007

代码实现

class Solution { public int waysToStep(int { if (n <= 2){ return n; } int[] dp = new int[n+1]; 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)% 1000000007; } return

最后

时间复杂度：O(n);

空间复杂度：O(n);

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。