算法训练营第09周学习笔记

回顾动态规划 递归，函数自己调用自己就是最基本的递归；递归、分治和回溯，其实就是定义一个问题的不同方面。分治，就是分而递归，如果不递归，用强制循环也是可以的，绝大部分用递归写分治是非常自然的机器思维方式。分治用递归的前提就是把递归模板准备好，然后准备数据和拆分问题，同时每个子问题都调分治函数递归求解，这样就得到一些中间的结果，把中间结果合并起来，再返回。排序、快排和归并排序就是典型的分治算法。 最近可重复子问题就是最大公约数：其本质是寻找重复性——>计算机指令集。 动态规划（Dynamic Programming） 1.Simplifying a complicated problem by breaking it down into simper sub-problems(in a recursive manner). 2.Divide & Conquer + Optimal substructure(分治+最优子结构) 3.顺推形式：动态递推

分治和动态规划的共性与差异： 动态规划和递归或者分治在本质计算步骤上没有区别，共性就是找到重复子问题；差异性是看有无最优子结构和中途可以淘汰次优解。

高阶的DP为什复杂？ 复杂度来源： 1.状态拥有更多维度（二位、三维、更多，甚至需要压缩）； 2.状态方程更加复杂； 3.需要跟高的“内功”、逻辑思维和数学能力。

编辑距离： 1.如果word1[i]与word2[j]相同，则dp[i][j]=dp[i-1][j-1]； 2.如果word1[i]与word2[j]不同，那么dp[i][j]可以通过 a)在dp[i-1][j-1]的基础上做replace的操作达到目的； b)dp[i-1][j]的基础上做insert操作达到目的； c)在dp[i][j-1]的基础上做delete操作达到目的； 取以上三者最小情况即可。