闵可夫司机
2022-10-17 16:41 华中科技大学 iOS开发
关注
通过率 72% 应该是超时了。
文字可能讲不明白，先看图吧。
在计算 14 的奇 dp 值时，要求黑线所指的和，求 12 的奇 dp 值时，求的是红线所指的和。可以发现其中绝大多数操作是重复的，红箭头所指的和就是 12 的奇 dp 值（如果不是 12 而是某个奇数则是 dp 值减一）。因此我们可以把求奇 dp 的操作优化为下面的操作（如果 x 是奇数则结果要减一），求偶 dp 也有类似的关系。这样就把时间复杂度从 O(n^2) 优化为了 O(n)。
查看原帖
1 评论
相关推荐
阿里云成长空间 741人发布 不愿透露姓名的神秘牛友
10-29 21:14
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 2025年终总结 #
171085次浏览 2884人参与
# 找工作，行业重要还是岗位重要？ #
85174次浏览 1685人参与
# 职场上哪些行为很加分？ #
306557次浏览 3448人参与
# 大家每天通勤多久？ #
69484次浏览 440人参与
# 你面试体验感最差/最好的公司 #
16515次浏览 268人参与
# 实习的内耗时刻 #
210894次浏览 1537人参与
# 一人说一个提前实习的好处 #
9932次浏览 197人参与
# 今年你最想重开的一场面试是？ #
3730次浏览 66人参与
# 互联网行业现在还值得去吗 #
46848次浏览 351人参与
# 秋招落幕，你是He or Be #
10586次浏览 215人参与
# 面试吐槽bot #
164946次浏览 814人参与
# 实习没事做是福还是祸？ #
16131次浏览 245人参与
# 重来一次，你会对开始求职的自己说 #
5746次浏览 143人参与
# 反问环节如何提问 #
126333次浏览 2663人参与
# 礼物开箱Plog #
617次浏览 21人参与
# 团建是“福利”还是是 “渡劫” #
6853次浏览 146人参与
# 工作中听到最受打击的一句话 #
6128次浏览 108人参与
# 我的第一份实习怎么找的 #
208474次浏览 1827人参与
# 比亚迪工作体验 #
74412次浏览 281人参与
# 大厂VS公务员你怎么选 #
74425次浏览 681人参与