动态规划，作为算法中比较实用用和好玩的一种，却常常给人一种神秘的面纱。

如果将其拆解，抽丝剥茧，会发现其有着通用的共识和套路，竟然是如此简单。

本文从简单开始，慢慢图解动态规划的那些套路。

从递归开始

学过编程的朋友应该都理解递归，按理不用多讲述，但是还是从它开始吧，从基本的开始：要计算从1到100，作为头脑的预热。

最直接想到的是一个for 循环挨个加就可，要啥递归？

但就是要用递归去做呢？

要计算sum(100)，则先计算sum(99)，再加上100就可；

要计算sum(99)？那就sum(98)，再加上99；

……
要计算sum(1)？它是最后一个了，直接return 1 即可。

# 从1到 N 的正数和 
def SUM(n):       
    if n <= 1:
        return n

    front = SUM(n-1)
    result = front + n

    return result

实际写代码肯定不会如上面那样写（一个迭代能搞定谁用递归？）。

只是想表达一个基本的的思路：处理一个大问题时候，拆分为小问题处理，再把子问题结果做整合，作为本问题结果，使得问题更简化。

我们可以清晰得到，递归的基本结构：

递归的基本结构:
1 结束条件处理；
2 子问题处理；
3 本层问题处理；
4 整合结果，返回。

好了弄懂递归问题了，那么动态规划问题就了解一半了，喝口茶休息下～

别急，我们继续慢慢看。

动态规划的结构

用递归来做动规，动态规划的结构，并没有比递归复杂太多，他们有着接近的结构（注：动规也可以不用递归来弄，用迭代也行，不讨论这个情况了），我们可以整理动态规划的简约公式：

动态规划 = 递归 + 存储化记忆

直接上动态规划的结构吧：

动态规划结构:
  1 结束条件处理
  2 记忆查找
  3 子问题处理
  4 本层问题处理
  5 整合结果存储
  6 整合结果返回

动态规划比递归多了2和5，也就是存储化记忆部分。

稍微复杂点的是，动态规划的子问题不会像递归那么直接，它可能有多个子问题要处理，所以在整合结果时候也会复杂一点点。

动态规划例子

直接看一个实际例子——莱文斯坦距离计算：

莱文斯坦距离：由一个字符串转成另一个字符串所需的最少编辑操作次数，编辑一次包括删除一个字符、插入一个字符、替换一个字符三种。莱文斯坦距离也是计算两个字符串的相似度问题。

比如：”abcd” 要转为”abc”，莱文斯坦距离为1，也就是把后面d删除，一次操作；

再比如：”abcd” 要转为”aked”，莱文斯坦距离距离为2，b替换为k，c替换为e，两次操作。

动态规划，通常都有一个递推（倒推）的过程，一般称为状态转移。把当前问题求解，拆分为一个或者几个子问题求解，再做整合。莱文斯坦距离问题，也是如此。

（为了讲述方便，先约定下，大写S[n] 表示长度为n 的字符串S，小写s[n] 表示S的第n个字母）。

长度为n的字符串S[n]，转为长度为m的字符串L[m]。

我们假定最后一次转换是最后一个字母，则最后一次转换，不外乎是下面几种情况（子问题拆分）：

1） S[n]转为某个字符串X[m-1]（X和L的前m-1个字符相同），之后增加一个字符；  

2） S[n]转为某个字符串X[m+1]（X和L的前m个字符相同），之后删除最后一个字符； 

3） S[n] 转为某个字符串X[m]（X和L的前m-1个字符相同），修改最后一个字符；    

上面说的变换是在最后一个字符的情况，但如果最短距离变化的不是在最后一个字符，而是在中间呢？

好问题，再认真分析，发现这种情况，囊括在情况3了，差异在于x[m]和l[m] 两个字母也相等，即最后一个编辑次数为0就等价了。

代码部分

用func = dp(s1, s2) 表示莱文斯坦距离(LevenshteinDistcance) 。

S到L如果是从情况1过来的，则LevenshteinDistcance 为：

    distcance1 = dp(s1, s2[:-1]) + 1
    # 等价 dp(s1, s2[:-1]) + dp("", s2[-1])

如果是从情况2过来的，则LevenshteinDistcance 为：

    distcance2 = dp(s1[:-1], s2) + 1
    # 等价  dp(s1[:-1], s2) + dp(s1[-1], "")

如果是从情况3过来的，则LevenshteinDistcance 为：

    distcance3 = dp(s1[:-1], s2[:-1])
    if s1[-1] != s2[-1]:
        # 最后一个字符不同，才需要增加距离
        distcance3 += 1
    # distcance3 = dp(s1[:-1], s2[:-1]) + dp(s1[-1], s2[-1])

（三个路径过来）三者取最小值，则是S到L的莱文斯坦距离了。

所以，整理代码有：

def dp(s1, s2):
    if s1 == s2:
        # 字符串相等，距离0
        return 0

    if s1 == "" or s2 == "":
        # 某个字符串为空，变化就等于非空的字符串长度了
        return len(s1) + len(s2)

    if len(s1) == 1 and len(s2) == 1:
        return 1 # 替换

    distcance1 = dp(s1, s2[:-1]) + 1
    # 等价 dp(s1, s2[:-1]) + dp("", s2[-1])

    distcance2 = dp(s1[:-1], s2) + 1
    # 等价  dp(s1[:-1], s2) + dp(s1[-1], "")

    distcance3 = dp(s1[:-1], s2[:-1])
    if s1[-1] != s2[-1]:
        # 最后一个字符不同，才需要增加距离
        distcance3 += 1
    # distcance3 = dp(s1[:-1], s2[:-1]) + dp(s1[-1], s2[-1])

    distcance = min(distcance1, distcance2, distcance3)

    return distcance

就酱紫？我们运行下，看看连云港（lianyungang）到石家庄（shijiazhuang）的莱文斯距离：

那么短的字符计算，运行时间17秒+，这性能接受不了吧。而且字符每长一个字符，运行时间指数增加。

等等，上面的代码，仅是递归而已，还不是动态规划，仅有动态，没有规划啊！

就好比你点个剁椒鱼头，结果上来一个清水鱼头没有剁椒，甚至上来是一碟剁椒没有鱼头，你抓狂不？

前面说过：

动态规划 = 递归 + 存储记忆。

说好的存储化记忆呢？

现在就加上。

由于计算dp(s1, s2)时候，有大量s1的子字符转换为s2的子字符的重复计算，重复计算都是被浪费掉的。

我们做个缓存，在计算前，先在缓存查找，有则返回，没有则计算，再存储后返回。

再整理的完整代码（比上面的，多了红色部分）：

上述代码定义了scores = {}作为缓存，利用python的tuple（元组）可以作为key 的特点，直接用(s1,s2) 作为scores的key，就省去了定义复杂的缓存设计了。

加上存储记忆之后，运行情况：

总结

动态规划 = 递归 + 存储记忆。#（第三次出现了）

做动态规划的过程，都可以写下面的函数框架（俗称自上而下编程），之后每个分支填上对应的代码就可。

动规最考头脑的部分在于子问题的拆分，不同问题有不同的分析，这个就看实际情况而定了。

相应的leetcode有（一次编辑问题）：https://leetcode.cn/problems/one-away-lcci/description/

其实就是判断其距离是否超过1。

（全文完）

（欢迎转载本站文章，但请注明作者和出处 云域 – Yuccn ）