【每日一题】4月24日题目精讲 dp

题号 NC17065
名称 子序列
来源 美团2018年CodeM大赛-复赛
戳我进入往期每日一题汇总贴~
往期每日一题题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

首先我们要知道如果满足 那么 也成立。

因为:

所以我们先维护出序列里任意两个元素是否能选在同一个子序列里面,然后类似最长上升子序列的方法——用f[i]表示在前i个数选若干个数其中第i个必须要选的方法数,显然 , j<i,且aj和ai能在一个子序列里。

一个小技巧:比大小可能会溢出十分不快乐,所以我们可以取个对数,这样就能把指数拿下来了。

看完邓老师的题解,记得去自己做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目5月1日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/776d9e2d18a84ac5be85ba83c1f4702b 码了好久
1 回复 分享
发布于 2020-04-23 17:34
https://blog.nowcoder.net/n/51e274b941494cceb92b63506ad85a90
点赞 回复 分享
发布于 2020-05-02 16:31
https://blog.nowcoder.net/n/716de9201e384729b4c378f9e0a04911
点赞 回复 分享
发布于 2020-04-30 18:05
https://blog.nowcoder.net/n/5c636c580c95470383158380bd07cb72 我觉得我写的挺清楚了,清楚姐姐
点赞 回复 分享
发布于 2020-04-30 12:55
https://blog.nowcoder.net/n/f948517d0ec2492aa0828d6568151466
点赞 回复 分享
发布于 2020-04-28 17:02
https://blog.nowcoder.net/n/4da1361e5077416ca339db5561c6c276
点赞 回复 分享
发布于 2020-04-28 15:41
https://blog.nowcoder.net/n/230c974f6cc54879b0281a32031b876e 清楚姐姐我又来啦
点赞 回复 分享
发布于 2020-04-28 14:53
https://blog.nowcoder.net/n/1e125d710d9c47299c528f791c99fc58
点赞 回复 分享
发布于 2020-04-27 23:41
https://blog.nowcoder.net/n/a7936bd6d1d546c9b595364ca3d6246d
点赞 回复 分享
发布于 2020-04-24 18:17
https://blog.nowcoder.net/n/0769c0f3e5534942bd5755f01de10b29
点赞 回复 分享
发布于 2020-04-24 17:55
https://blog.nowcoder.net/n/6751e7af71ac4d31a6b59d64f47f87cb
点赞 回复 分享
发布于 2020-04-24 16:27
https://blog.nowcoder.net/n/4b5c3dd10ad7460da41013f5dacbd447
点赞 回复 分享
发布于 2020-04-24 14:50
https://blog.nowcoder.net/n/56a9581d920f4642be3689823842ec35
点赞 回复 分享
发布于 2020-04-24 14:03
https://blog.nowcoder.net/n/1943489187bc48f2a066eeebbcb29b59
点赞 回复 分享
发布于 2020-04-24 11:35
https://blog.nowcoder.net/n/3f3037b8c5594f5c9603d1f0d345e48c
点赞 回复 分享
发布于 2020-04-24 09:35
https://blog.nowcoder.net/n/b5fc1fd1fe9d4455af86f12ed50038d1
点赞 回复 分享
发布于 2020-04-24 02:42
https://blog.nowcoder.net/n/fa24930a5c5c4e52b69b1294deb9d8d3
点赞 回复 分享
发布于 2020-04-24 00:51
https://blog.nowcoder.net/n/092b0ebaad8d45aa882c21ab28ae8250
点赞 回复 分享
发布于 2020-04-23 22:10
https://blog.nowcoder.net/n/8c492ac8818f4385ab7eb174583ec716
点赞 回复 分享
发布于 2020-04-23 21:39
https://blog.nowcoder.net/n/0c09dbc31a5d41e6aed1bd97112c7bda
点赞 回复 分享
发布于 2020-04-23 19:19

相关推荐

27届末九,由于是女生,身边人几乎没有就业导向的,自学只能跟着网课,没人指导,很迷茫。下图是我目前的简历,不知道有需要修改的地方吗?求拷打。下面是目前的学习情况:目前算法过完了一遍力扣100和代码随想录,不过不是很熟,面经看了小林coding、JavaGuide,有一些没用过的技术看得不是很明白,掌握得不是很扎实。再加上常年跟黑马网课听思路,真正自己动手写代码的时间很少,这让我一直不敢投简历,总觉得内里空虚。项目没准备好面试相关的问题,简历上相应的考点不熟。如此种种。。。看到很多很多学长学姐大佬们的面经,愈发觉得面试可怕,自己没准备好,总担心自己是不是无望后端开发了。看到牛客很多同届以及更小一届的同学都找到实习了,很希望自己也能找到实习。而自己又好像摸不到后端学习的门路,只能不断赞叹黑马虎哥写的代码真优雅!微服务架构实在巧妙!消息队列、redis、sentinel、nacos、mybatisplus等等的引入都会让我赞叹这些工具的设计者的巧思,以及包括但不限于Java语言的优雅。然而只是停留在了解的程度,并不熟练。我是很希望能够继续深入探索这些知识的,只不过有一大部分时间都花在学校课程上了。我感觉我被困住了,我一方面必须保证我能够有个不错的学业分使我能有我几乎不想选择的读研退路(还有个原因是复习不全我会焦虑考试挂科,因此我会做好全面的准备,而这一步很费时间),一方面在B站学习各种网课,一方面得考虑提升自己并不扎实的算法基础,另一方面还得准备八股面经。这让我有点苦恼,我好像没那么多时间,因为绝大部分时间都花在了复习学校科目中了。我好像处处用时间,但收效甚微。想问问各位大佬是怎么平衡时间的呢?算法、项目和八股是怎么准备的呢?有什么高效的方法吗?谢谢您们花时间阅读我的稿件!
菜菜狗🐶:大胆投,我当时也是害怕面试,投多了发现根本约不到面🤡
投递哔哩哔哩等公司6个岗位
点赞 评论 收藏
分享
A_SOUL_Off...:疑似加班加出幻觉了
点赞 评论 收藏
分享
评论
点赞
2
分享

创作者周榜

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