冯耀宗seo视频教程,网站优化的核心不包括,建网站来做什么,网站的底部导航怎么做动态规划 Dynamic Programming DP 准则
动态规划的本质#xff0c;是对问题状态的定义和状态转移方程的定义。
动态规划是通过拆分问题#xff0c;定义问题状态和状态之间的关系#xff0c;使得问题能够以递推#xff08;或者说分治#xff09;的方式去解决。
如何拆分…动态规划 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 状态数。
