动态规划做多了以后，总结的相关知识
动态规划 Dynamic Programming DP
准则
动态规划的本质，是对问题状态的定义和状态转移方程的定义。
动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
如何拆分问题，才是动态规划的核心。
而拆分问题，靠的就是状态的定义和状态转移方程的定义。
以LIS为例，重新定义这个问题：
给定一个数列，长度为N，
设F_{k}为：以数列中第k项结尾的最长上升子序列的长度.
求F_{1}..F_{N} 中的最大值.
对于F_{k}来讲，F_{1} .. F_{k-1}都是F_{k}的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第1..k-1中某项结尾的LIS。
上述的新问题F_{k}也可以叫做状态，定义中的“F_{k}为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。
之所以把F_{k}做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。
上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。
比如，对于LIS问题，状态转移方程为：
以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。
a. “缓存”，“重叠子问题”，“记忆化”
这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，不是动态规划的核心。
b. “自上而下”，“自下而上”
“递归”：递归是递推式求解的方法，连技巧都算不上。
怎么实现dp？答：两种常用的方法。（仅仅涉及一般问题）
1. 自下而上：通过正向的loop，求出所有状态对应的值，然后找出max或者min。 优缺点：速度慢，但是相对节省空间。
2. 自上而下：通过递归的方法，需要求解f(x)，则必须知道f(y)，要知道f(y)，必须求f(z). 优缺点：速度快，只用算需要的值，但是要调用堆栈，浪费空间。
c. "无后效性"，“最优子结构”
上述的状态转移方程中，等式右边不会用到下标大于左边i或者k的值，这是"无后效性"的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
这个性质叫做最优子结构；
而不管之前这个状态是如何得到的
这个性质叫做无后效性。
在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。
d. 关于复杂度的分析
时间复杂度O （状态数 * 每个状态下所对应的决策数）。
空间复杂度O （状态数）。
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/104039077
- 点赞
- 收藏
- 关注作者
评论（0）