程序员面试金典08.01-三步问题

原题(来源Leetcode)

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

示例1:

输入: n = 3
输出: 4
说明: 有四种走法

示例2:

输入: n = 5
输出: 13

提示:

  1. 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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月18日 11:08
下一篇 2020年6月21日

相关推荐

  • leetcode912-排序数组

    原题 给定一个整数数组 nums,将该数组升序排列。 示例 1: 输入: [5,2,3,1] 输出: [1,2,3,5] 示例 2: 输入: [5,1,1,2,0,0] 输出: […

    算法 2020年3月31日
    0350
  • 程序员面试金典01.07-旋转矩阵

    原题(来源Leetcode) 给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。 不占用额外内存空间能否做到? 示例 …

    算法 2020年4月7日
    0410
  • leetcode56-合并区间

    原题 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]…

    算法 2020年4月16日
    0160
  • leetcode83-删除排序链表中的重复元素

    今天打算多刷几道算法题 原题 给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->…

    算法 2020年6月16日
    01350
  • leetcode945-使数组唯一的最小增量

    原题 给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 示例 1: 输入: [1,2,2] 输出: 1…

    算法 2020年3月22日
    0630
  • leetcode328-奇偶链表

    原题 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空…

    算法 2019年12月16日
    0130
  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格…

    算法 2020年4月12日
    0130
  • leetcode34--在排序数组中查找元素的第一个和最后一个位置

    原题 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数…

    算法 2020年1月3日
    0150
  • 海量数据-两种方法解决top k问题

    假如提供一百万个数据(甚至更大)的无序数组,如何从中获取最大的k个元素? 最容易想到的是先降序排序然后获取前k个元素,那假设我们用最常用的O(nlogn)级别的排序算法,要获取to…

    2020年4月4日
    0220
  • leetcode242-有效的字母异位词

    原题 https://leetcode.cn/problems/valid-anagram/description/ 解法 (针对进阶场景,若字符串中存在unicode字符) fu…

    算法 2024年3月26日
    040

发表回复

登录后才能评论