Fork me on GitHub

动态规划法应用实例构造回文(Python3)


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

1、方法简介

1.1 最长公共子串

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

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


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

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

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

1.2 最长公共子序列

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


伪代码如下:

1
2
3
4
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编写代码

构造回文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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("请输入字符串:")) # 先实例化类再调用

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

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

符合牛客网在线判题系统规范的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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()来去除空格和多余的符号,如下图


修改代码以后就成功啦。嘿嘿。花了一晚上研究这道题,对算法和动态规划有了一点初步的了解,让我对算法有了更多的认识,不再觉得算法是一些太高大上太难的东西,以后还得努力学习!冲鸭。

本文结束啦 感谢您阅读
路漫漫其修远兮 吾将上下而求索