首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
牛客868052144号
天津科技大学 计算机类
发布于河南
关注
已关注
取消关注
@zanejins:
25 动态规划DP--递推求解
题目来源2008年华中科技大学计算机保研机试真题题目描述N阶楼梯上楼问题:一次可以走两阶或一阶,问有多少种上楼方式。(要求采用非递归)输入说明输入包括一个整数N,(1<=N<90)。输出说明可能有多组测试数据,对于每组数据, 输出当楼梯阶数是N时的上楼方式个数。样例展示输入:4复制输出:5问题分析这个问题就是一个典型的递推问题。若我们把N分别等于1,2,3...的答案依次排列成一个数列,我们即需求这个数列每一个数的值。我们定义f[n]为数列中的第n个数字,同时F[n]为台阶总数为n时的上台阶方式总数。首先,我们必须确定数列之间的递推关系。当n大于2时,我们考虑每一种上台阶方式的最后一步,由于只有两种行走的方法,因此它只可能是从n-1阶经过一步走到n阶,或者从n-2阶经过2步走到n阶。我们分别考虑这两种走法,即我们将此时所有的上台阶方式按照最后一步走法的不同分为两类,分别确定这两类的上台阶数目。这样我们就确定达到n阶楼梯总的上楼方式个数为F[n-1]和F[n-2]的和,即F[n]=F[n-1]+F[n-2]。这就是我们这个数列的递归关系。由初始值F[1]=1,F[2]=2,我们就能得到所有F[n]的值。C++代码#include<iostream>using namespace std;typedef long long ll;ll F[100];int main() { F[1]=1; F[2]=2; for(int i=3;i<=90;i++) { F[i]=F[i-1]+F[i-2]; } int n; while(scanf("%d",&n)!=EOF) { printf("%lld\n",F[n]); } return 0;}不容易系列之一题目描述大家常常感慨,要做好一件事情真的不容易,确实,失败比成功容易多了!做好“一件”事情尚且不易,若想永远成功而总从不失败,那更是难上加难了,就像花钱总是比挣钱容易的道理一样。话虽这样说,我还是要告诉大家,要想失败到一定程度也是不容易的。比如,我高中的时候,就有一个神奇的女生,在英语考试的时候,竟然把 40 个单项选择题全部做错了!大家都学过概率论,应该知道出现这种情况的概率,所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语,我们可以这样总结:一个人做错一道选择题并不难,难的是全部做错,一个不对。不幸的是,这种小概率事件又发生了,而且就在我们身边:事情是这样的——HDU 有个网名叫做 8006 的男性同学,结交网友无数,最近该同学玩起了浪漫,同时给 n 个网友每人写了一封信,这都没什么,要命的是,他竟然把所有的信都装错了信封!注意了,是全部装错哟!现在的问题是:请大家帮可怜的 8006 同学计算一下,一共有多少种可能的错误方式呢?输入说明输入数据包含多个多个测试实例,每个测试实例占用一行,每行包含一个正整数 n(1<n<=20),n 表示 8006 的网友的人数。输出说明对于每行输入请输出可能的错误方式的数量,每个实例的输出占用一行。样例说明样例输入:23样例输出:12问题分析同样的,在该例子中我们也容易得到规模较小时的错装方式数量。如n为1时,数量为0;n为2时数量为1.我们按照n的取值顺序将所有的错装方式数量排列为一个数列,同样F[n]表示数列里第n个数的取值,F[n]同时代表n个信封的错装方式总数。接下来我们确定该数列的递推关系。当n大于3时候,我们考虑n封信全部装错的情况。将信封按照顺序由1到n编号。在任意一种封装方案中,假设n号信封里面装的是k号信封的信,而n号信封里的信则封装在m号信封里。我们按照k和m的相等与否将总的装错方式分为两类。若k不等于m,交换n号信封和m号信封的信后,n号信封里装的恰好是对应的信,而m号信封中错装k号信封的信,即除n号信封外其余n-1个信封装错,其装错方式为F[n-1],又由于m的n-1个可能取值,这类错装总数为(n-1)F[n-1]。也可以理解为,在n-1个信封错装的F[n-1]的基础上,将n号信封所装的信与n-1个信封中任意一个信封交换后,得到所有信封的全部装错的方式数。另一种情况,若k等于m,交换n号信封和m号信封后,n和信封和m号信封里面装的恰好是对应的信,这样除她们之外剩余的n-2个信封全部错装,其错装方式为F[n-2],又由于m的n-1个取值,这类错装方式总数为(n-1)* F[n-2]。也可以理解为,在n-2个信封全部错装的基础上,交换最后两个信封中的信(n号信封和1到n-1号信封中任意一个)共有n-1种选择,使得所有的信封全部错装的方式数。综上所述:F[n]=(n-1) * F[n-1] + (n-1) * F[n-2]C++代码#include<iostream>using namespace std;typedef long long ll;ll F[21];int main() { F[1]=0; F[2]=1; for(int i=3;i<=20;i++) { F[i]=(i-1)*F[i-1]+(i-1)*F[i-2]; } int n; while(scanf("%d",&n)!=EOF) { printf("%lld\n",F[n]); //输出 } return 0;}吃糖果https://www.nowcoder.com/questionTerminal/72015680c32b449899e81f1470836097C++代码//话说这应该是和爬楼梯一样吧#include<iostream>using namespace std;typedef long long ll;ll dp[21];int main() { dp[1]=1; dp[2]=2; for(int i=3;i<=20;i++) { dp[i]=dp[i-1]+dp[i-2]; } int n; while(scanf("%d",&n)!=EOF) { printf("%d\n",dp[n]); } return 0;}
点赞 0
评论 0
全部评论
推荐
最新
楼层
秋招专场
校招火热招聘中
官网直投
相关推荐
slin__
05-19 17:54
已编辑
门头沟学院 计算机类
对不起,我找不到工作影响学校的生存了
点赞
评论
收藏
转发
震云
05-08 16:18
陕西师范大学 计算机类
25届实习简历,求佬们拷打
点赞
评论
收藏
转发
superjayhurry
05-27 21:29
National University of Singapore 计算机类
日常实习求捞
本科北理24届,目前已经拿nus研究生offer 准备在剩下这几个月找段实习, 目前想找一段后端开发的实习 主要语言是Java, 之前有小公司java后端的经历,也有一段学校区块链科研经历 找日常实习已经找麻了,没人搭理,有没有好心佬组里有需求内推下(手动牛泪)
实习,投递多份简历没人回复怎么办
我的实习求职记录
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
给你们预测一下今年的秋招!
3179
2
...
阿里体检完还没发正式offer
2697
3
...
【🎁】25届硬件牛牛互助计划(1期)
2531
4
...
深圳蟑螂真的很可怕吗
2365
5
...
拿了蓝桥杯c++b组国二,水平怎么样,找后端开发工作有多大优势?
2348
6
...
毕业了!
2053
7
...
二本开发转测试,面试成功
1950
8
...
海康威视,25暑期实习,软件开发岗
1723
9
...
腾讯音乐还是58同城
1670
10
...
海康暑期实习
1657
正在热议
#
和牛牛一起刷题打卡
#
13664次浏览
1263人参与
#
通信硬件薪资爆料
#
255578次浏览
2406人参与
#
不去互联网可以去金融科技
#
3406次浏览
48人参与
#
牛客帮帮团来啦!有问必答
#
1091578次浏览
16298人参与
#
面试被问第一学历差时该怎么回答
#
18160次浏览
199人参与
#
简历中的项目经历要怎么写?
#
14239次浏览
189人参与
#
工作两年想退休了
#
19211次浏览
239人参与
#
实习生应该准时下班吗
#
92997次浏览
704人参与
#
你收到了团子的OC了吗
#
530480次浏览
6290人参与
#
你已经投递多少份简历了
#
338281次浏览
4905人参与
#
简历无回复,你会继续海投还是优化再投?
#
23440次浏览
329人参与
#
你怎么评价今年的春招?
#
12377次浏览
192人参与
#
简历中的项目经历要怎么写
#
481785次浏览
8758人参与
#
晒一晒我的offer
#
3768736次浏览
58040人参与
#
担心入职之后被发现很菜怎么办
#
39515次浏览
327人参与
#
本周投递记录
#
220810次浏览
5375人参与
#
硬件人的简历怎么写
#
81810次浏览
849人参与
#
我想象的工作vs实际工作
#
105711次浏览
1700人参与
#
2022毕业生求职现身说法
#
23587次浏览
338人参与
#
你的秋招进行到哪一步了
#
396559次浏览
6677人参与
#
产品人求职现状
#
56794次浏览
822人参与
牛客网
牛客企业服务