动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。

1、方法简介

1.1 最长公共子串

最长公共子串要求在原字符串中是连续的。

在动态规划中，你要将某个指标最大化。在这个例子中，你要找出两个单词的最长公共子串。hish 和 fish 都包含的最长子串是什么呢？
单元格中的值通常就是你要优化的值。在这个例子中，这很可能是一个数字：两个字符串都包含的最长子串的长度。
坐标轴很是这两个单词。因此，网格可能类似于下面这样。

从表格中我们可得得知最长公共字串长度为3，是”ish”。

实现这个公式的伪代码类似于下面这样：

if word_a[i] == word_b[j]:  ←---------两个字母相同
  cell[i][j] = cell[i-1][j-1] + 1
else:  ←------------------------------两个字母不同
  cell[i][j] = 0

1.2 最长公共子序列

子序列只需要保持相对顺序一致，并不要求连续。

伪代码如下：

if word_a[i] == word_b[j]:      ←--------两个字母相同
  cell[i][j] = cell[i-1][j-1] + 1
else:     ←------------------------------两个字母不同
  cell[i][j] = max(cell[i-1][j], cell[i][j-1])

2、[编程题] 构造回文

牛客网上有这么一道腾讯2017暑期实习生编程题，题目如下图：

这道题目就非常适合使用动态规划法来编写。
通过上文的介绍，我们已经可以使用动态对话法来求最长公共子序列，按照题目要求，把字符串s反转过来，求他们的最长公共子序列，再减去原先字符串s的长度不就是最小的删除字符个数了吗？

2.1 使用Python3编写代码

构造回文

import numpy as np


class Solution:
    def longestPalindrome(self, s):
        str1 = s
        str2 = str1[:][::-1]  # 将字符串反转
        cell = np.zeros((len(str1) + 1, len(str2) + 1))  # 字符串长度+1
        for i in range(len(str1)):
            for j in range(len(str2)):
                if str1[i] == str2[j]:
                    cell[i][j] = cell[i - 1][j - 1] + 1
                else:
                    cell[i][j] = max(cell[i - 1][j], cell[i][j - 1])
        print(len(str1) - int(np.max(cell)))


Solution().longestPalindrome(input("请输入字符串："))  # 先实例化类再调用

当我在本地写好代码运行可以成功了以后，到牛客网的在线编辑器中再次编辑却是一直运行不了。后来再知道原来牛客网的在线编辑器有自己的规范，不能随意使用第三方包，输入也要有规定的样式。点击这里查看牛客网在线判题系统使用帮助。

于是我又把我的代码修改了一下。

符合牛客网在线判题系统规范的代码

import sys


class Solution:
    def longestPalindrome(self, s):
        str1 = s
        str2 = str1[::-1]
        length = len(str1)
        cell = [[0] * (length + 1) for i in range(length + 1)]  # 字符串长度+1
        for i in range(len(str1)):
            for j in range(len(str2)):
                if str1[i] == str2[j]:
                    cell[i][j] = cell[i - 1][j - 1] + 1
                else:
                    cell[i][j] = max(cell[i - 1][j], cell[i][j - 1])
        return length - max(max(cell))


if __name__ == '__main__':
    for line in sys.stdin:
        print(Solution().longestPalindrome(line.strip())) //使用sys.stdin获取的字符串有"\n"需要使用strip()来去除空格和多余的符号，如下图