再谈动态规划

index-picture

1.最长公共子序列

• 问题情景：
  假设你管理着网站dictionary.com。用户在该网站输入单词时，你需要给出其定义。
  但如果用户拼错了，你必须猜测他原本要输入的是什么单词。例如，假设Alex不小心输入了fosh。那怎么知道他原本想输入的是fort还是fish呢?

• 解答：
  如果用最长公共子串，两个单词的最长公共子串长度都为2，所以改用最长公共子序列

网格图（图片来源《算法图解》）

最终判断想要输入的是fish这个单词！

• Python3实现代码：

  def LCS(string1,string2):
        len1 = len(string1)
        len2 = len(string2)
        res = [[0 for i in range(len1+1)] for j in range(len2+1)] # 创建一个二维数组，赋初始值为0
  
        # i为行，j为列
        for i in range(1,len2+1):
            for j in range(1,len1+1):
                if string2[i-1] == string1[j-1]:
                    res[i][j] = res[i-1][j-1]+1
                else:
                    res[i][j] = max(res[i-1][j],res[i][j-1])
         return res,res[-1][-1]
  

2.最长公共子串

• 问题情景：
  求fish和hish的最长公共子串

• 解答：
  

  网格图（图片来源《算法图解》）

• python3代码：

    def LCString(string1,string2):
        len1 = len(string1)
        len2 = len(string2)
        res = [[0 for i in range(len1+1)] for j in range(len2+1)] # 创建一个二维数组，赋初始值为0
        result = 0 # 存储当前最长子串的长度
  
        # i为行，j为列
        for i in range(1,len2+1):
            for j in range(1,len1+1):
                if string2[i-1] == string1[j-1]:
                    res[i][j] = res[i-1][j-1]+1
                    result = max(result, res[i][j])            
         return result