动态规划-字符串编辑距离

什么是动态规划？通俗地理解来说，一个问题的解决办法一看就知道（穷举），但不能一个一个数啊，你得找到最优的解决办法，换句话说题目中就会出现类似“最多”、“最少”，“一共有多少种”等提法，这些题理论上都能使用动态规划的思想来求解。动态规划与分治方法类似，都是通过组合子问题的解来求解原问题，但它对每个子问题只求解一次，将其保存在表格中，无需重新计算，通常用于求解最优化问题——《算法导论》。

动态规划-cnblog-字符串编辑距离