动态规划-leetcode-5

​​0️⃣python数据结构与算法学习路线​​ 学习内容：

• 基本算法：枚举、排序、搜索、递归、分治、优先搜索、贪心、双指针、动态规划等…
• 数据结构：字符串(string)、列表(list)、元组(tuple)、字典(dictionary)、集合(set)、数组、队列、栈、树、图、堆等…

题目：

给你一个字符串 ​​s​​​，找到 ​​s​​ 中最长的回文子串（从左向右和从右向左读一样的的字符串）。

输入输出：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

解题思路：

需要一种能够快速判断原字符串的所有子串是否是回文子串的方法，于是想到了「动态规划」。「回文」天然具有「状态转移」性质。回文去掉两头以后，剩下的部分依然是回文。

如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；
如果一个字符串的头尾两个字符相等，才有必要继续判断下去。
如果里面的子串是回文，整体就是回文串；
如果里面的子串不是回文串，整体就不是回文串。
 

第 1 步：定义状态
dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j]。

第 2 步：思考状态转移方程
在这一步分类讨论（根据头尾字符是否相等），根据上面的分析得到：
dp[i][j] =Ture (if s[i] == s[j])

dp[i + 1][j – 1]
说明：「动态规划」事实上是在填一张二维表格，由于构成子串，因此 i 和 j 的关系是 i

看到 dp[i + 1][j – 1] 就得考虑边界情况。

边界条件是：表达式 [i + 1, j – 1] 不构成区间，即长度严格小于 2，即 j – 1 – (i + 1) + 1

这个结论很显然：j – i

如果子串 s[i + 1..j – 1] 只有 1 个字符，即去掉两头，剩下中间部分只有 11 个字符，显然是回文；
如果子串 s[i + 1..j – 1] 为空串，那么子串 s[i, j] 一定是回文子串。
因此，在 s[i] == s[j] 成立和 j – i

第 3 步：考虑初始化
初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true 。

事实上，初始化的部分都可以省去。因为只有一个字符的时候一定是回文，dp[i][i] 根本不会被其它状态值所参考。

第 4 步：考虑输出
只要一得到 dp[i][j] = true，就记录子串的长度和起始位置，没有必要截取，这是因为截取字符串也要消耗性能，记录此时的回文子串的「起始位置」和「回文长度」即可。

第 5 步：考虑优化空间
因为在填表的过程中，只参考了左下方的数值。事实上可以优化，但是增加了代码编写和理解的难度，丢失可读和可解释性。在这里不优化空间。

注意事项：总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要。

算法实现：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size             return s

        dp = [[False for _ in range(size)] for _ in range(size)]

        max_len = 1
        start = 0

        for i in range(size):
            dp[i][i] = True

        for j in range(1, size):
            for i in range(0, j):
                if s[i] == s[j]:
                    if j - i                         dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                else:
                    dp[i][j] = False

                if dp[i][j]:
                    cur_len = j - i + 1
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i
        return s[start:start + max_len]

出现问题：

1. s[::-1] 反向排列列表

s1 = s[l:0:-1]输出 “daba”

2. 输入：dp = [[False for _ in range(5)] for _ in range(5)]

输出：[[False, False, False, False, False], [False, False, False, False, False], [False, False, False, False, False], [False, False, False, False, False], [False, False, False, False, False]]

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net