|
不久前不少人留言说要介绍介绍动态规划，今天我们就来介绍介绍什么是动态规划。 动态规划算法是现实中非常的一个算法。之前我们做过一个判断送餐的骑手能否在规定时间内送完手头的外卖，就用了这个算法。（当然，算出来的只是一个理论的结果，但可以防止骑手一下子接太多单，最后造成用户投诉）。后面如果有机会会介绍一下这个问题的实现。这个问题挺有趣的。可以抛出来给大家思考一下。
相比于直接搜索，动态规划往往更加高效。现在我们通过5个问题，来认识什么是动态规划。 第一，什么是动态规划？ 动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 重点在后半句，把问题分解成简单子问题进行解决。与之类似的有另外一个算法，分治。他俩最大的区别在于子问题之间是否相关联。 第二， 动态规划的思想？ 动态规划的思想很简单，就是分解问题求解，然后再合并子问题的解。 第三， 哪些问题可以用动态规划来解决？ 接下来的内容可能比较难以理解，我们通过一个经典的面试题，然后接着讲。
1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。 上面的题目。如果我们假设f[3]表示以a[3]结尾的最长上升子序列，那么转移到它的子问题一定要是最优的。也就是从f[2]也要求是最优的。 2.无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。 如同上面那个问题，我们从左往右计算，右边后算的结果不会影响到左边的结果，即满足无后效性。 3.子问题重叠性质。即同不同的子问题，可能都需要计算同一个另外的子问题。 当我们要求已5为结尾的序列最多有多少个的时候，我们需要知道已3结尾的有多少个。当我们求以9结尾的序列最多有多少个的时候，我们又要去计算以3结尾的有多少个。这就是子问题重叠了。 第四， 动态规划题目的解题策略大概怎么样。 动态规划一般解决问题的流程可以如下面： 初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态 1.首先是划分阶段，将问题分解为子问题。 2.表示状态，如何用相应的数据结构表示每个子问题的状态。 3.确定转移方程，子问题与子问题之间的关系已经方程的转移。 4.确定边界。初始状态的边界，何时结束之类等。 我们用上面的这个教程，来解决上面的LIS问题。 首先，划分状态，我们确定了一下子问题，以第i个数结尾的最长上升子序列是多少。 其次，表示状态，我们用f[i]表示以第i个数结尾的最长上升子序列是多少。 第三转移方程，我们另j<i，不难看出，需要a[j]<a[i]才进行状态转移。所以f[i] = max{f[j] 1},a[j]<a[i] 第四，边界条件,初始f[i] = 1,因为序列最少可以是他本身。结束条件为f[n-1](base 0) 第五, 动态规划的题目大致可以分为几类？ 动态规划常见的模型有4大类：
好了，懂了这五个问题，基本上就算入门了。其实算法这种东西，并不是靠看一篇教程就能够马上理解的。后面，我们会在《一日一算法题》的系列中，再继续谈一谈动态规划。 最后其实有一个有趣的问题，有没有人想尝试用《算法入门----枚举算法》枚举算法解决上面的LIS问题呢。复杂度又是多少呢？ 你是否大概知道什么是动态规划 (单选)
0人
0%
大概明了，给小编加鸡腿
0人
0%
不懂，关注小编坐等其他题目
原创不易，欢迎大家关注我的头条号，也可以关注我的微信公众号（ddpcyh）,后续会提供算法学习资料，一起来学习算法吧。 |
|
|
