定义啥的就不多说了，反正我有自己的理解就行。例题是，最长公共子序列和最长公共子字符串的动态规划求解过程
目录
一、递归和动态规划
二、动态规划求解步骤
三、最长公共子序列
四、最长公共子字符串
一、递归和动态规划
动态规划是算法的一种和 ”递归“有相似之处，也有不同。动态规划和分治递归，都是为了拆分出更小的子问题，对子问题逐一解决，最后得到结果。两者不同的地方在于，递归的子问题拆分是在代码实现中体现的，利用栈将大问题拆分成子问题，最后由最小的子问题，逐个反馈合并成大问题所需要的结果。是一个自上而下拆分，再自下而上计算的过程。而动态规划的子问题的拆分过程并不是在代码中体现，而是由程序员在编码前分析好。在编码时，直接求解最小的问题，通过自下而上的方式解决大问题。
动态规划相比于"递归"的优势,就是计算效率更高，子问题只需要求解1次就可以。动态规划的缺点：可能会再空间上增大代价。
例如如下式子：
当计算 f(8) 的值时， 用递归的方式就是
f(8) = f(7) +f(6) = ( f(6) + f(5) ) + f(6) ........
用递归的方式可以看出，在计算f(8)的值时 f(6) 会被重复计算两次，再往下 f(5) 会被重复计算3次，以此类推。
而动态规划的目的就是为了每个子问题最多求解1次，自下而上的方式解决问题就是
f(2) =f(1) + f(0) =1
f(3) =f(2) + f(1) =2
.....
结果如下图Excel所示
在Excel中展示的求解逻辑，就是动态规划，每个子问题只需求解1次，自底向上的求解方式。实际上，上图展示的Excel在代码中可以在空间上进行优化，只需要用两个变量分别存储最新的f(x-1) ,f(x-2) 就行。
二、动态规划求解步骤
问题抽象化：将一个具体的问题变成一个通用的问题确认结果变量f(x1,x2.....)和 抽象参数集合{x1,x2,x3......}分析抽象参数和结果变量的关系将分析出来的结果整合成递归的表达式根据表达式，作表得到动态规划的求解过程*分析过程的优化(本文不具体说明)三、最长公共子序列
分析字符串X = ABCBDAB 和 Y =BDCABA 的 最长公共子序列(注：序列不是字符串，序列可以不连续)
1.1：问题抽象化
分析字符串 和 的最长公共子序列
1.2 参数有两个 Xn 和 Ym ，结果变量有长度 L (n,m)和公共子序列 Z(n,m)。
1.3 如果 和 的最长子序列是
当时,那么必然满足，且和的公共子序列为
当 ， 时，那么和Ym的公共子序列为Zk
当 ， 时，那么Xn和的公共子序列为Zk
1.4因此：
1.5
长度L的Excel表如下
最大公共子序列Z的Excel表如下
四、最长公共子字符串
分析字符串X = ABABDAB 和 Y =BDCABA 的 最长公共子字符串(即连续的序列)
1.1：问题抽象化
分析字符串 和 的最长公共子串
1.2 参数有两个 Xn 和 Ym ，结果变量有长度 L (n,m)和公共子串Z(n,m)。临时变量，当前在判定的公共子字符串Z'(n,m)，在判定的公共子字符串长度L'(n,m)
1.3 如果 和 的最长子字符串是
当判和，当≠时，那么<,>必然不是的公共字符串，如果那么必然满足至少是 X，Y长度为1的公共子字符串，如果还满足,那么至少是 X，Y长度为21的公共子字符串,以此类推...因此
所以最长公共字符串，就是历史比较出来的最长公共字符串 和当前作比较公共字符串作对比，如果当前作比较公共字符串比历史最长的都要长，那么就覆盖历史的最长公共子字符串
如果 和 的最长子字符串是
L‘(n,m) >= (历史比较出的)最长字符串长度L(n,m),那么当前比较出的公共子字符串就是最长的; 如果L‘(n,m) < L(n,m) ,那么最长公共字符串不变
最后得到的结果是ABA
