介绍
动态规划并不是一种具体的算法,而是一种思想,个人觉得就是缓存+枚举,把求解的问题分成许多阶段或者多个子问题,然后按顺序求解各子问题。前一子问题的解为后一子问题提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
所以动态规划一般用来求最优解(对子问题进行决策),求种类数(对子问题进行加和)
先分享几个经典的动态规划实现,后续再分析几个面试题
最长上升子序列
来源:LeetCode 300.最长上升子序列
描述:给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,本文标题:动态规划:更高效的穷举!
本文链接:https://blog.quwenai.cn/post/8842.html
版权声明:本文不使用任何协议授权,您可以任何形式自由转载或使用。







还没有评论,来说两句吧...