一)多阶段决策过程的优化问题2 )动态规划的基本概念和基本模型构成1 )阶段和阶段变量2 )状态和状态变量3 )决策、决策变量、决策许可集合4 )战略和最佳战略(思维核心)5.状态转移方程式) 33330
2 .无后效性原则：如果现在所做的不影响以前所做的，这个阶段以后过程的发展变化只与这个阶段的状态有关，与这个阶段以前的过程所经历的状态无关
(四)基本动态规划模型的应用1 .数塔问题)1)主题)2)构想a .爆搜：从头搜索，深入搜索至数塔底部，最后将返回值返回最上面
b .记忆化检索：记录每个经过的点，将返回的值存入1个record数组，即使下次遇到record数组，如果有记录也会直接返回
c.Dp (正向传输)状态转移方程) f(I ) ) j )=max ) f(I-1 )，f(I-1 ) ) a ) I ) ) j )；
Dp (反向推动)状态转移方程(f ) I ) j )=max ) f ) I1 ) j )，f ) I1 ) ) a ) I ) ) j )；
)3)二维码a .爆搜
b .记忆化检索
c.Dp (顺按) ) ) )。
Dp )反推
2 .最长不下降子序列(1)主题(2)思路朴素算法n^n
单调性优化nlogn(Dalao详细信息链接) ) ) ) ) )。
a .注意如何输出路径。 将C数组(需要额外设置n的容量)放置在此时队列的位置，并在输出时从末尾开始扫描。 如果输出c[i]=len，则len--，len变为0，此时，更新的位置不会被错过最长不下降的子序列的末尾一级，仅存在确保更新的扩展)直接踢下。 例如，数据7 9 16 38 49 10，根据策略应该是7 9 16 38 49，但是更新完毕的f序列在7 9 10 38 49不能直接串联输出，需要用序列进行标记。 这样，后面的东西就会自动被过滤掉。 有点优秀呢。 请参考这个dalao
(3)优化)上述单调性优化nlogn )4)伪码朴素算法n^n
单调性优化nlogn
3 .最长公共子序列(1)主题)2)思路：将状态f[x][y]设为到s1的x位置和到s2的y位置。 此时，最长公共子串相对于s1[x]，如果不在最长公共子串中，则在f[x][y]=f[x-1][y] s1[x]==s2[y]的情况下，f [ x ] [ y ]=f [ x ] 但是，后者必须满足s1[x]==s2[y] )
)3)特殊情况优化a .主题：
b .思路：首先按照一个规则依次存储第一队列，然后按照相同规则处理第二队列。 此时，因为第二队列的原始最长公共子序列的性质cqdkj不变，并且第一队列是有序的，所以如果第二队列是有序的子序列，则它是公共子序列，并且问题被转换为第二队列的最长上升子序列
c .伪代码
4 )伪代码暴力DP(n^n ) ) ) ) )。
(5)变形最长上升公共子序列)首先考虑n4侧的单纯Dp，用f[i][j]表示的话，是s1到I，s2到j，那时的最长上升子序列的长度。 此时，只需要s[i]==s[j]s[h]==s[k]，s[I]
优化：如果两个字符串相同，则进行处理，如果不相同，则继承以前的f[i][j-1]，在f[i][j-1]中检索最大的，返回到上一个。
未完成的后续~~~
转载于：https://www.cn blogs.com/Sean ocean/p/10990503.html