补充下,动态规划。特点1:一般是求最值问题,是一种智慧的穷举;特点2:存在重叠子问题及最优子结构,(1)最优子结构通俗的将就是分解的子问题是相互独立的,比如已知班级最高分求解全校最高分(这其实不是这个动态规划的问题,其实我想说的是最优子结构不是动态规划特有的)(2)重叠子问题:最简单的例子是斐波那契数列,画出递归树很容易知道有很多重叠子问题,以至于其递归算法是指数的复杂度,解决重叠子问题有两种思路:自上而下--备忘录,自下而上--动态规划;一般用的自下而上,但是不是所有的问题都可以用自下而上,这是就用自上而下。动态规划思路:定义dp数组及明确初始条件;状态转移;确定遍历方向及返回值;(能否状态压缩?--可选)
点赞

相关推荐

迷茫的大四🐶:自信一点,我认为你可以拿到50k,低于50k完全配不上你的能力,兄弟,不要被他们骗了,你可以的
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务