写点什么

算法题每日一练: 青蛙跳台阶

作者:知心宝贝
  • 2023-04-26
    江苏
  • 本文字数:887 字

    阅读完需:约 3 分钟

算法题每日一练: 青蛙跳台阶

一、问题描述

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


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

二、题目要求

运行限制

  • 最大运行时间:1s

  • 最大运行内存: 128M

样例

输入:2  输出:2输入:7  输出:21输入:0  输出:1
复制代码

考察

1.动态规划入门2.建议用时5~15min
复制代码

三、问题分析


做动态规划需要几步,就像冰箱装大象一样,分成三步:

第一步:含义搞懂

通常动态规划都会用数组 dp[]存放东西,那存放在数组里面的究竟是什么?


这要看题目问我们什么,这一题就问青蛙跳台阶的方案数嘛,那么 dp[i]就代表第 i 个台阶有 dp[i]个方案,它问什么我们就存什么。

第二步:变量初始

dp[0]=1             题目样例给了dp[1]=1             1个台阶跨一步就到dp[2]=2             2个台阶可以跨1个台阶再跨1个,也可以一次性跨2个,所以两种方案dp[3]=3             3个台阶每次跨1个、先跨1个再跨2个、先跨2个再跨1个     ......
复制代码


初始变量一般找 2~5 个就行,下面才是重头戏啊!

第三步:关系归纳

搞清楚数组的含义和初始值之后,我们求的是第 n 个台阶方案数,题目又没给,怎么办?


找规律,做归纳总结,看看和前面的台阶方案有什么关系,这一步很重要,规律找不好直接芭比 q。



仔细看一下第二步的规律,后一个是不是等于前面两个相加,所以第 n 个公式为:


dp[n]=dp[n-1]+dp[n-2]。


三步走,打完收工!

四、编码实现

#include<iostream>using namespace std;int numWays(int n){    if(n<=1) return 1;    int dp[n+1],i;    dp[0]=1,dp[1]=1;//初始化变量    for(i=2;i<=n;i++)    {      //规律        dp[i]=(dp[i-1]+dp[i-2])%1000000007;//取模别忘了    }    return dp[n];//返回结果}int main(){  int k;  cin>>k;//输入台阶数目  cout<<numWays(k);//赋值给动态规划功能的函数  return 0;}
复制代码

五、测试结果

六、总结与提高

如果题目改成:


一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶......一直到 n 级台阶。求该青蛙跳上一个 n (0 <= n <= 100)级的台阶总共有多少种跳法,做完之后可以在评论区交流结果

发布于: 刚刚阅读数: 4
用户头像

知心宝贝

关注

公众号:穿越计算机的迷雾 2022-03-07 加入

生于尘埃 溺于人海 死于理想高台

评论

发布
暂无评论
算法题每日一练: 青蛙跳台阶_数据结构_知心宝贝_InfoQ写作社区