上台阶简单动态规划或者用循环

ゝ一世哀愁。 2022-07-16 02:08 140阅读 0赞

上台阶

*  热度指数：2859时间限制：3秒空间限制：32768K
 *  本题知识点： [递归][Link 1] [动态规划][Link 2]
 *  [ 算法知识视频讲解][Link 3]

## 题目描述 ##

有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或者二级，要走上m级，共有多少走法？注：规定从一级到一级有0种走法。

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100。为了防止溢出，请返回结果Mod 1000000007的值。

测试样例：

3

返回：2

import java.util.*;
    
    public class GoUpstairs {
        
        int[] count = new int[100];
        public int countWays(int n) {
        	for(int i=0;i<100;i++){
                count[i]=-1;
            }
            return cal(n);
        }
        public int cal(int n){
            if(count[n]!=-1)return count[n];
            if(n<=3) return n-1;
            else {
                count[n]=(cal(n-1) + cal(n-2))%1000000007;
                return count[n];
            }
        }
    }

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=591
[Link 2]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=593
[Link 3]: http://www.nowcoder.com/courses/1

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划 - N步台阶问题

该文转载，因所看文章没有放原文链接，故找不到原文链接题目分析问题本质：斐波那契数列 > 令跳法为f(n)， > > 如果n=1：\{ \{1\}\}，f(1

阳光穿透心脏的1/2处/ 2022年12月15日 15:27/ 0 赞/ 164 阅读

相关青蛙跳台阶 - 动态规划

青蛙跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算

雨点打透心脏的1/2处/ 2022年11月22日 12:53/ 0 赞/ 170 阅读

相关简单的动态规划

认识动态规划以下是一段描述斐波那契数列的简单代码。本质是一个递归的方案，它的计算过程是不断的将大计算拆分成小计算，最后再对小计算的结果进行合并。然而递归方案的时间复杂度

你的名字/ 2022年11月19日 11:29/ 0 赞/ 275 阅读

相关【动态规划】硬币面值组合（上台阶）

问题 1分2分5分的硬币三种，组合成1角，共有多少种组合？有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少中组合可以组成n分钱？

逃离我推掉我的手/ 2022年08月09日 03:16/ 0 赞/ 198 阅读

相关动态规划题目（二）——跳台阶

动态规划题目（二）——跳台阶 1. 题目描述一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。求总共有多少总跳法，并分析算法的时间复杂

待我称王封你为后i/ 2022年08月06日 01:08/ 0 赞/ 163 阅读

相关 poj 1065 贪心或者动态规划

Wooden Sticks <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000M

偏执的太偏执、/ 2022年08月03日 11:55/ 0 赞/ 188 阅读

相关 hdu 5339 动态规划或者dfs

Untitled Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (

灰太狼/ 2022年08月03日 08:19/ 0 赞/ 125 阅读

相关上台阶简单动态规划或者用循环

上台阶热度指数：2859时间限制：3秒空间限制：32768K 本题知识点： [递归][Link 1] [动态规划][Link 2] [ 算法知识视频讲解]

ゝ一世哀愁。/ 2022年07月16日 02:08/ 0 赞/ 141 阅读

相关字符串上的简单动态规划

因为数据结构快学串了，以前又做过一些字符串dp的题，今天突然就想把它们写在一起吧。直接开始问题1：给两个字符串，求最长公共子串问题2：给两个字符串，求最长公共子序列

我就是我/ 2022年05月12日 01:48/ 0 赞/ 196 阅读

相关动态规划——简单理解

动态规划的基本步骤 1. 找出最优解的性质，并刻划其结构特征的。（寻找最优解的子问题结构） 2. 递归的定义最优解。（根据子问题结构建立问题的递归解式求解最优值） 3

妖狐艹你老母/ 2022年05月09日 03:16/ 0 赞/ 221 阅读