当前位置: 首页 > news >正文

淄博市建设局网站河南seo快速排名

淄博市建设局网站,河南seo快速排名,小型营销企业网站建设策划,设计类公司网站数楼梯(加强版) 题目背景: 小明一天放学回家,看到从1楼到2楼共有n个台阶,因为好奇,他想尝试一下总共有几种方案到二楼?他可以1步,2步,3步的跳,不能跳3步以上. 他试了很多次都没有解决这个问题,于是请求聪明的你帮忙解决这个问题. 题目描述: 1楼到2楼楼梯有n级台阶。小明每…

数楼梯(加强版)

题目背景:

  小明一天放学回家,看到从1楼到2楼共有n个台阶,因为好奇,他想尝试一下总共有几种方案到二楼?他可以1步,2步,3步的跳,不能跳3步以上.
  他试了很多次都没有解决这个问题,于是请求聪明的你帮忙解决这个问题.

题目描述:

1楼到2楼楼梯有n级台阶。小明每次可以爬一格、走两格或者跨三格。问最终有几种方案到二楼?答案对998244353取模。

输入格式:

一行一个数n。

输出格式:

一行一个数,表示方案数。

输入输出样例

输入 #1:

3

输出 #1:

4

输入 #2:

5

输出 #2:

13

提示说明:

 n≤1000  
 时间:1000ms   
 空间:256M  
 (上楼梯时不能往回走)
 如果觉得这道题太难可以前往P1255先做数楼梯简单版:
 https://www.luogu.com.cn/problem/P1255

思路:

  1.暴力法

  很容易看出来,这是一道递归题,我们可以用暴力递归来解决。

#include<iostream> 
using namespace std; 
static const int mod=998244353;
long long sum=0;
int n;
long long fun(int x){if(x==n)return 1;if(x>n)return 0;long long s1=0,s2=0,s3=0;s1+=fun(x+1)%mod;s2+=fun(x+2)%mod;s3+=fun(x+3)%mod;return (s1+s2+s3)%mod;
}
int main(){cin>>n;cout<<fun(0)<<endl;		return 0;
}

但是这个份代码会超时,非常慢,所以要进行优化!

2.递推法

我们用 f(x) 表示爬到第 x 级台阶的方案数,考虑最后一步可能跨了一级台阶,也可能跨了两级台阶,所以我们可以列出如下式子:
f(x)=f(x−1)+f(x−2)
它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解,因为每次只能爬 1 级或 2 级,所以 f(x) 只能从 f(x−1)和 f(x−2) 转移过来,而这里要统计方案总数,我们就需要对这两项的贡献求和。

  以上是动态规划的转移方程,下面我们来讨论边界条件。我们是从第 0 级开始爬的,所以从第 0 级爬到第 0 级我们可以看作只有一种方案,即 f(0)=1;从第 0 级到第 1 级也只有一种方案,即爬一级,f(1)=1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下,根据转移方程得到 f(2)=2,f(3)=3,f(4)=5,……,我们把这些情况都枚举出来,发现计算的结果是正确的。

  我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n)的实现,但是由于这里的 f(x) 只和 f(x−1)) 与 f(x−2)有关,所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

#include<iostream> 
using namespace std; 
static const int mod=998244353;
void fun(int n){long long max[1001];int i=0;max[0]=1;max[1]=2;max[2]=4;for(int j=3;j<n;j++)max[j]=(max[j-1]+max[j-2]+max[j-3])%mod;cout<<max[n-1]<<endl;
}
int main(){int n;cin>>n;fun(n);		return 0;
}

总结:

  对于这道题,有些像斐波那契数列,需要将递归进行优化才可以解决。

题目链接:

数楼梯(加强版) - 洛谷https://www.luogu.com.cn/problem/U267577

http://www.khdw.cn/news/25353.html

相关文章:

  • 0基础建站教程军事新闻 今日关注
  • wordpress fonts外链seo
  • 做网站的公司 经营范围搜狗站长平台验证不了
  • 网站轮播代码宝鸡seo
  • 专业房产网站建设怎么在百度上发布自己的信息
  • 做独立电商网站国产免费crm系统有哪些
  • 丰台网站建设最新国际消息
  • 做程序开发的网站中小企业网站优化
  • 做导购网站 商品社交媒体营销策略有哪些
  • 网站建设优化需要懂那些知识交友平台
  • 怎么查出这个网站是谁做的百度seo搜索引擎优化
  • 青岛市网站制作游戏推广在哪里接活
  • 白云商城型网站建设成品网站建站空间
  • 品牌形象设计毕业论文关键词排名优化
  • 郴州网站建设哪家做的好河南省网站
  • 企业做网站怎么做老王搜索引擎入口
  • 精美化妆品网站模板百度旗下的所有产品
  • 龙岗做网站多少钱网站一级域名和二级域名区别
  • 苹果软件做ppt模板下载网站有哪些内容潍坊seo按天收费
  • 网站现在如何做推广有什么平台可以推广
  • 合肥做网站的软件公司网络广告公司
  • 手工活接单正规平台盐城网站优化
  • 南昌有限公司 网站百度搜索引擎原理
  • 深圳做网站联系电话好的营销网站设计公司
  • 上海人事人才网上海有实力的seo推广咨询
  • 哪个网站有教做面食银川网页设计公司
  • 网站过期了怎么办网站注册搜索引擎的目的是
  • 江门建设造价信息网站公众号seo排名优化
  • 中山快速建站合作常用的网络营销方法
  • 池州网站制作哪家好写文章在哪里发表挣钱