原题（来源Leetcode）
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入: n = 3
输出: 4
说明: 有四种走法
示例2:
输入： n = 5
输出： 13
提示：
- n范围在[1, 1000000]之间
解法
思想
动态规划，注意溢出的问题。
代码
class Solution {
public int waysToStep(int n) {
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+1; i++) {
dp[i] = (dp[i-1] + (dp[i-2] + dp[i-3]) % 1000000007) % 1000000007;
}
return dp[n];
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e7%a8%8b%e5%ba%8f%e5%91%98%e9%9d%a2%e8%af%95%e9%87%91%e5%85%b808-01-%e4%b8%89%e6%ad%a5%e9%97%ae%e9%a2%98/
相关推荐
-
剑指offer06-从尾到头打印链表
原题（来源Leetcode） 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例1: 输入： head = [1,3,2] 输出： [2,3,1] 限制： ...
-
leetcode86-分隔链表
原题 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head...
-
leetcode85-最大矩形
原题 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例： 输入: [ ["1","0","1","0","0"...
-
leetcode367-有效的完全平方数
原题 给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。 说明： 不要使用任何内置的库函数，如 sqrt。 示例1： ...
-
leetcode98-验证二叉搜索树
原题 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和...
-
leetcode279-完全平方数
原题 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出...
-
leetcode4-寻找两个有序数组的中位数
这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m...
-
leetcode39-组合总和
原题 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates ...
-
leetcode34--在排序数组中查找元素的第一个和最后一个位置
原题 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数...
-
leetcode430-扁平化多级双向链表
原题 您将获得一个双向链表，除了下一个和前一个指针之外，它还有一个子指针，可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示...
