题解 | #跳台阶扩展问题#

跳台阶扩展问题

http://www.nowcoder.com/practice/953b74ca5c4d44bb91f39ac4ddea0fee

跳台阶问题 (plus)

这个问题看了【数据结构与算法】大佬的操作
写出他的状态转移方程:

f(n)=f(n-1)+.....f(1) //doge:我只能想到这一步

如果跳了一层,剩下n-1层也可如上式:

f(n-1) = f(n-2) + .....f(1)
化简可得:
f(n) = 2* f(n-1)
即:
f(n)/f(n-1) = 2

#include<iostream>
using namespace std;

int main(){
    int num;
    cin >> num;
    cout<< (1 << num-1) <<endl; 
}
全部评论
方程错了,按你说的,f3 = f2 + f1,而很显然f2 = 2, f1 = 1,那么f3 = f2+f1 = 2+1 = 3,与题意不符,转移方程应该是在右边加个1,即:fn = fn-1+fn-2+...+f2+f1+1
点赞 回复 分享
发布于 2022-09-04 00:32 湖北
我爱小明这种方法可以,可以这样理解,每台台阶上都有一个昆虫,青蛙跳上去吃,不往后跳,那么每个昆虫要么吃,要么没有吃,
点赞 回复 分享
发布于 2022-08-29 07:16 浙江
这里差一种可能,就是直接一下就跳到n
点赞 回复 分享
发布于 2022-08-29 07:09 浙江
我也学过一点dp,但是这种状态转移方程还是要基本检验一下,我反正验证不对
点赞 回复 分享
发布于 2022-03-25 22:37
不好意思,抱歉了,我语气不是很好,我觉得你还是换一种思考方式吧。你可以这样想,每一阶台阶都有两种状态,跳上或者没跳上,而最后一节台阶是一定要踏上的,所以状态是跳上,这样也就是2的n-1次方,再一次向你抱歉
点赞 回复 分享
发布于 2022-03-25 22:35
你在恶心人吧,浪费老子时间看你代码!!!
点赞 回复 分享
发布于 2022-03-19 22:22
f3=f2+f1吗
点赞 回复 分享
发布于 2022-03-19 22:03

相关推荐

湫湫湫不会java:写的很杂,连自己都不知道找什么工作的感觉,只是要份工作。针对自己稍微有点优势的方向好好整份简历投投吧,然后这杂的简历就辅助投投,因为自己认为的优势可能也不是很大的优势all in可能失业,自己也没有啥很想的方向还是可以用这通用的碰碰运气吧,加油
点赞 评论 收藏
分享
Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
06-27 18:53
门头沟学院 Java
这样才知道自己不适合搞代码,考公去咯
只爱喝白开水:我也发现不适合搞代码,打算转非技术方向了
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务