动态规划问题

问题来自于我在leetcode刷到的一个找最长回文子串的问题，自己使用了简单的暴力搜索，Google之后发现了利用动态规划解决该问题，感觉很巧妙，记录一下。

我的新书《LangChain编程从入门到实践》 已经开售！推荐正在学习AI应用开发的朋友购买阅读！

简述

• 动态规划就是把一个复杂问题分阶段简化，逐步化简为简单问题的过程，动态规划中包含三个重要的概念：最优子结构,边界，状态转移公式。
• 分析：基本思路是对任意字符串，如果头和尾相同，那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。如果头和尾不同，那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分的最长回文子串的较长的那一个。

  P[i,j]: 表示第i到第j个字符的回文子串数 
  dp[i,i]=1
  dp[i,j]=dp[i+1,j−1]+2 if s[i]=s[j]
  dp[i,j]=max(dp[i+1,j],dp[i,j−1]) if s[i]!=s[j]

  代码实现

  def longestPalindrome(self, s: str) -> str:
      start=0
      maxstr=0
      for i in range(len(s)):
          if i-maxstr>=1 and s[i-maxstr-1:i+1]==s[i-maxstr-1:i+1][::-1]:
              start = i-maxstr-1
              maxstr+=2
              continue
          if  i-maxstr>=0 and s[i-maxstr:i+1]==s[i-maxstr:i+1][::-1]:
              start = i-maxstr
              maxstr+=1
      return s[start:start+maxstr]

  参考链接

  看动画轻松理解「递归」与「动态规划」
  Longest Palindromic Substring 最长回文子串 Python 四种解法