Nginx配置 Git centos7安装 图像处理 mysql安装 unity SQLMAP list iis build datagrid icons jquery去掉空格 change事件 jq选择子元素 oracle分页关键字 bootstrap日历控件 linux管道符 less的比较级 html下拉框默认选中 爬虫数据清洗 重置hosts python中time java实战 java的接口 java获取当前年份 java函数式接口 java获取ip地址 java框架学习 java输出 java的安装 php实例代码 qq飞车剧情辅助 rndis驱动下载 亚索刀光特效包 图解设计模式 beatedit hexworkshop 安卓刷机精灵 系统工具箱
当前位置: 首页 > 学习教程  > 编程语言

剑指 Offer 10- II. 青蛙跳台阶问题(动态规划)1

2020/11/4 14:48:01 文章标签:

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e97(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1: 输入&a…

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2
示例 2:

输入:n = 7
输出:21
示例 3:

输入:n = 0
输出:1
提示:

0 <= n <= 100

解法一:动态规划

时间复杂度 O(N) : 计算 f(n)需循环 n次,每轮循环内计算操作使用 O(1)。
空间复杂度 O(1): 几个标志变量使用常数大小的额外空间。

class Solution {
    public int numWays(int n) {
        if (n == 0 || n== 1) return 1;
        int[] res = new int[n+1];
        res[1] = 1;
        res[2] = 2;
        for (int i=3; i<=n; i++) {
            res[i] = (res[i-2] + res[i-1]) % 1000000007;
        }
        return res[n];
    }
}

 

 


本文链接: http://www.dtmao.cc/news_show_350207.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?