Dynamic Programming_Leetcode_部分动态规划题分析
5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。Example 1:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd" Output: "bb"
思路：
该题中动态规划并不是最优解，但却是一个较容易理解的思路
设dp[i][j]是一个布尔值，且其意味着字符串s第i位到第j位截取出来的片段是否为回文。
即 if dp[i][j] == True: s[i:j+1] 为回文
关键思路：
如何判定dp[i][j]是True?
当dp[i+1][j-1] == True 并且s[i] == s[j]时， dp[i][j] = True
解释一下：
为了知道s[i:j+1]是否是回文
首先,s[i] 必须等于s[j]，首尾必须呼应，这是规矩
其次只要s[i+1:j+1-1]是回文，那两边同时加上一样的字符的s[i:j+1]也必定是回文.
那么如何知道s[i+1:j+1-1]是回文？同样需要两个条件:s[i+1] == s[j-1] and s[i+1+1:j+1-1-1]
那么如何知道s[i+2:j-1]是回文？....
dp就可以开始规划了:
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
l, r = 0, 0
dp = [[False for i in range(len(s))] for j in range(len(s))]#创造动态表
for gap in range(len(s)):#跨度从最小的0开始判定
for i in range(len(s)-gap):
j = i+gap
dp[i][j] = (j-i <=1 or dp[i+1][j-1]) and s[i] == s[j]#为了避免out of range, 长度小于等于2且首尾相等的字符串直接判定为True
if dp[i][j] and j-i+1 > r-l:#如果长度大于原记录，则把左右坐标替代
l,r = i, j
return s[l:r+1]
更多精彩
