小田田的算法笔记--动态规划

小田田的算法笔记 ---- 动态规划
7.1 背景
与分治算法情况不同，直接实现递推的结果，会导致不止一次递归调用，因此这种技术采取自底向上的方式求递推值，并把中间结果存储起来以便以后用来计算所需要的解。利用这种技术可以设计出特别有效的算法来解决许多组合最优化问题，亦可以改善蛮力搜索算法的时间复杂性。
比如Fibonacci : f(n) = f(n-1) + f(n-2)
=2f(n-2) + f(n-3)
=3f(n-3) + 2f(n-4)
=…????
会导致巨大数量的重复调用，如果用数组存储结果，那么就会简单许多。
7.2 最长公共子序列问题
问题描述： 在字母表中，分别给出两个长度为 n 和 m 的字符串 A 和 B，确定在 A 和 B中最长公共子序列的长度。
蛮力： 指数级别/(ㄒoㄒ)/~~
核心思想：

示例：


7.3 矩阵链相乘
问题描述： 求算矩阵M1M2…Mn的最有效方法
蛮力：/(ㄒoㄒ)/~~

优化算法思想：

示例：

算法MATCHAIN：
输入：n个矩阵的链的维数对应于正整数数组r[1…n+1],其中r[1…n]是n个矩阵的行数，r[n+1]是Mn的列数。
输出：n个矩阵相乘的数量乘法的最小次数。

复杂度分析：