1. 问题定义：

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。简而言之，就是相对顺序不变的一个序列。

为了解释方便，此处选取 hizh 和 fish 两个较短的字符串进行演示

2. 基础算法

解决思路：
- 将问题分割为小问题，从单个字母开始比较，逐渐扩张到整个字符串（看了解决步骤就明白了）
- 创建一个二维数组，用来存储每一步的结果。每次填完一行后再填第二行。

填第一行
- 第一行第一列(1,1) 。表示字符串f和字符串h公共序列长度
  - f和h不同，填0
  - 结果为0
- 后三个同理，
  - (1,2): f与hi公共子序列长度。
    - f与i不相同,为0
    - 而由(1,1)可知，f与h公共子串为0。
    - 结果：0+0=0
  - (1,3): f与hiz公共子序列长度。
    - f与z不相同,为0
    - 而由(1,2)可知，f与hi公共子串为0。
    - 结果：0+0=0
  - (1,4): f与hizh公共子序列长度。
    - f与h不相同，为0
    - 而由(1,3)可知， f与hiz公共子串为0。
    - 结果：0+0=0

填(2,1)。fi与h公共子序列长度。
- i与h不相同，为0
- 而由(1,1)可知
- f与h公共子串为0。
- 结果：0+0=0

填(2,2)。fi和hi
- i与i相同。为 1
- 由(2,1)可知，fi与h公共子序列长度为0
- 由(1,2)可知，f和hi公共子序列长度为0。
- 取两者较大值 0
- 结果：1+0=1
- 即：(2,2)值为 1 + max{ (1,2)的值 , (2,1)的值 } = 1

填第二行剩下的
- (2,3): fi与hiz公共子序列长度，
  - i与z不相同,为0
  - 由(2,2)可知，fi与hi公共子序列长度为1。
  - 由(1,3)可知，f和hiz公共子序列长度为0。
  - 取两者较大值 1
  - 结果：1+0=1
- (2,4): fi与hizh公共子序列长度
  - i与h不相同，为0
  - 由(2,3)可知，fi与hiz公共子序列长度为1。
  - 由(1,4)可知，f与hizh公共子序列长度为0
  - 取两者较大值
  - 结果：1+0=1

同样步骤填第三行：

第四行：

最终结果为2

3. 隐藏问题（重要）

在背包问题中解决方法和该问题的基本算法基本相同，但并没有此隐藏问题，有兴趣的可以查一下看看。算法图解中也以背包问题作为动态规划的入门

亲自按照上面的方式算下fishi和hizhii。是不是出现问题了？先自己仔细想想问题出在那里。

请看此图：

我们按照上面算法一步步得做，最终却出现了问题： 算法告诉我们填2，但大脑告诉我们填1

出现问题原因：i在(2,2)处已经相同了一次，因此此处无法再次计数。也就是说，只有在特殊情况下，该算法才能正常执行。

如果依旧使用该算法，可以通过记录是否相同过来解决此问题，但相对比较麻烦。此处进行算法改进。

4. 改进算法

这依旧是动态规划，只是每步的计算方式有些变化而已

有一个方式可以避免多次相同带来的问题：就是：看左上方的数值

而字符不相同的，就选取左边或上边的最大值。相当于：

最终算法：

5. 代码示例

感兴趣的也可以使用递归完成。此处为了直观构建了数组进行存储，而没有使用递归方式

import numpy

def main(str1: str, str2: str):
    m, n = len(str1), len(str2)
    ans = 0
    # 多一行一列，从1开始，省去边界判断问题
    dp = numpy.zeros((m+1, n+1), dtype=int)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                ans = max(ans, dp[i][j])
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    print(dp)
    return dp[-1][-1]

if __name__ == "__main__":
    print(main("fishi", "hizhii"))