1 动态规划

简单理论

  我们总是听到见到动态规划这个词，到底怎么定义动态规划呢？来自国外的一个编程大师指出：
  In a nutshell, dynamic programming is recursion without repetition.
  In a nutshell是一句英语俗语，就是“简单地说”。这句话翻译过来就是，动态规范，就是没有重复的递归。动态规划分为三步：
  第一步 定义子问题
  第二步 写出与子问题的递归方式
  第三步 解决不能继续拆分的基本问题
  动态规划，不过是把问题拆分为子问题，去除重复的运算。说起来非常简单，但是分好几种场景，常见的是以下几种场景

1. 一维动态规划
2. 二维动态规划
3. 内部动态规划
4. 树状动态规划
5. 子集合动态规划

一维动态规划

  我举个一维动态规划的例子：
  一个数字，写成1，3，4的和，有多少种方式？
  例如5，可以写成以下几种方式：
$$\begin{gathered} 5 \\ =1+1+1+1+1 \\ =1+1+3 \\ =1+3+1 \\ =1+4 \\ =3+1+1 \\ =4+1 \end{gathered}$$
  总共6种方式。
  那这个问题怎么解决呢？
  首先定义子问题，5的种类可以分为1 + 4，3+2，4+1三种形式。也就是5可以拆分为4的种类，2的种类，1的种类三个子问题。定义函数f(x)为某个数字写成1，3，4的和的种类，那么这是个分段函数，分段函数分可递归部分定义域和不可递归部分定义域。可递归部分也就是f(x) = f(x-1)+f(x-3)+f(x-4)。但是递归公式里有x-4，所以x至少为5，这个是可递归部分定义域。所以x为1， 2， 3， 4的四种情况就需要我们手动计算，这就叫不能继续递归的子问题，这也是不可递归部分的定义域。这四个不能递归的子问题答案我已经手动算出来了：
$$\begin{gathered} f(1)=1 \\ f(2)=1 \\ f(3)=2 \\ f(4)=2+1+1=4 \end{gathered}$$
  那么代码就简单了,存入数组要错一位,因为数组从0开始嘛。于是python代码如下：

def f(n):
    data = [1, 1, 2, 4]
    if (n < 5):
        return data[n - 1]
    for i in range(4, n): 
        data.append(data[i - 4] + data[i - 3] + data[i - 1])
    return data[n - 1]
1
2
3
4
5
6
7

  当然，这个代码执行起来空间复杂度非常高。可以优化为只用长度为5的数组来缓存，因为后面的计算最多只用到了前面第四个数组项。

二维动态规划

  二维动态规划，最常见的是面试题，最长子字符串问题。这里的最长子串是这样的规则，举个例子:
  x: ABCBDAB
  y: BDCABC
  那么最长字串是加粗的BCAB，长度为4。
  这个问题，我在数据结构中讲过，所以我不能抄袭自己，就直接抛个链接出来吧：最长子串问题。
  而另一个经典的二维动态规划问题是回文问题，举个例子，回文palindrome是指正反都起来都一样的文字，比如pop，上海自来水来自海上。现在请问一个不是回文的字符串，如何插入最少的字符，使之变成回文。
  举个例子：Ab3bd，插入d和A，就变成了dAb3bAd或者Adb3bdA。
  按照斯坦福大学定义的动态规范步骤，我们一步一步地解决这个问题。
  第一步是定义子问题：
  $D_{ij}$函数是使$x_i$~$x_j$变成回文的最少字符串数量的函数。当然，动态规划大部分场景下，都是用一维数组或多维数组存储函数值，所以也可以把这个函数当成数组。
  第二步是寻找递归：
  假设一个最短的回文$y_{1\sim k}$包含了子字符串$x_i$~$x_j$，那只有三种情况，要么左边补字母，要么右边补字母，要么x首尾相等（但中间不一定是回文哦）。
  也就是$y_1=x_i$ 或$y_k=x_j$,如果从左边补齐,那么就有这个例子：
  y=abcdedcba x=edcba
  如果从右边补齐，那么就有这个例子:
  y= abcdedcba x=abcde
  如果从中间插入，那么有这个例子：
  y= abcdedcba x=abcdea
  那么y去掉头尾，就是一个新的回文，可能存在三种情况：
  一是$x_{i+1,j}$的解比如：
$$x_{i+1,j}=bcde{y}_{2,k-1}=bcdedcb$$
  二是$x_{i,j-1}$的解，比如：
$$x_{i,j-1}=edcb{y}_{2,k-1}=bcdedcb$$
  还可能是$x_{i+1,j-1}$的解，比如xy完全相等，x首尾相等（但中间不一定是回文哦）。所以就有了递归公式：
$$D_{ij}=\{\begin{array}{ll}1+min(D_{i+1,j},D_{i,j-1})& x_i\ne x_j\\ D_{i+1,j-1}& x_i=x_j\end{array}$$
  递归的终点是一个字符串或两个相同的字符串，因为一个字符串和两个相同的字符串本身是回文。
  那么就是循环代码了啊,因为j比i大，所以只要填充上三角矩阵就行了，先初始化一个二维数组，假如是长度5的字符串：
$$\left[\begin{array}{ccccc}0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right]$$
  然后按这个循环,按左上到右下的斜方向扫描就行了。所以代码很简单啊:

# _*_ coding:utf-8 _*_

def palindrome(s):
    n = len(s)
    d = [[0 for _ in range(0, n)] for _ in range(0, n)]
    # t代表斜向扫描的初始列
    for t in range(1, n):
        # i 代表行号
        for i in range(0, n - t):
            # j代表扫描列
            # 寻找相邻想等的情况
            j = i + t
            if t == 1 and s[i] == s[j]:
                d[i][j] = 0
            elif s[i] == s[j]:
                d[i][j] = d[i + 1][j - 1]
            else:
                d[i][j] = 1 + min(d[i + 1][j], d[i][j - 1]) 
    return d[0][n - 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

  测试代码：

from com.youngthing.mathalgorithm.palindrome import palindrome

if __name__ == '__main__':

    #测试数据
    print(palindrome('abcde'))
    print(palindrome('我是12是我'))
    print(palindrome('Ab3bd'))
1
2
3
4
5
6
7
8

  测试结果:

4
1
2
1
2
3

  这个代码可以继续优化，因为二维数组的下半部分没有用，所以可以不要，以节省内存。