力扣刷题记录

动态规划

第一例 最长回文子串的问题分析和解题思路

---

---

前言

提示：这里可以添加本文要记录的大概内容：
本人新手，写博客纯属自我记忆，方便回顾，不喜勿喷

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、动态规划是什么？

就是直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

二、解决问题的步骤

1.问题描述

给你一个字符串 s，找到 s 中最长的回文子串。
1 <= s.length <= 1000
s 仅由数字和英文字母组成
注意：子串是连续的

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

输入：s = “cbbd”
输出：“bb”

2.问题分析

求最长回文子串的问题可转换为：当从第 i 个字符到第 j 个 字符组成的子串为最长回文子串，求解 i 和 j

3.问题解决步骤

1.状态定义：

定义dp[ i ][ j ] 表示 s 的第 i 个字符到第 j 个字符组成的子串，是否可构成回文子串
true 代表区间 [i,j] 为回文串
false 代表区间 [i,j] 不为回文串

2.状态转移方程：

dp[ i ][ j ] 能否构成回文子串，取决于两个因素

• 当前首位元素相同，s[i] == s[j]
• 前面的子串是回文的，dp[i+1][j-1] == true

3.状态转移方程补充特殊情况

上面第二个用例，s = “cbbd”，当 left = 1，right = 2 时，做的判断是：

s[1] == s[2] -> true
dp[2][1] -> false
从而导致 d[1][2] 错误的置为 false
错误的根源是，当「首尾元素紧挨着」的时候 left + 1 和 right - 1 引起的问题

因此，根据「首尾元素是否紧挨着」重新整理下状态转移方程

• 当首尾元素紧挨着，right - left == 1
  如果首尾元素相同，可构成回文串
  如果首尾元素不同，不构成回文串
• 当首尾元素中间有隔着的，right - left > 1
  当前首尾元素相同 s[i] == s[j]，且前面的子串是回文的 dp[i+1][j-1] == true，可构成回文串

4.问题解决步骤

1.初始化二维数组

例：

2.代码如下（示例）

class Solution {
    
public:
    string longestPalindrome(string s) {
    
       int n=s.size();
       vector<vector<bool>>dp(n,vector<bool>(n,false));
       for(int i=0;i<n;i++)
       {
    
           dp[i][i]=true;
       }
       int begin=0;
       int maxlength=1;
       for(int left=n-1;left>=0;left--)
       {
    
           for(int right=left+1;right<n;right++)
           {
    
               if(right-left==1)
               {
    
                   if(s[left]==s[right])
                   {
    
                       dp[left][right]=true;
                   }
                   else{
    
                       dp[left][right]=false;
                   }
               }
               else{
    
                   if(s[left]==s[right]&&dp[left+1][right-1]==true)
                   {
    
                       dp[left][right]=true;
                   }
                   else{
    
                       dp[left][right]=false;
                   }
               }
               if(dp[left][right]==true&&right-left+1>maxlength)
               {
    
                   begin=left;
                   maxlength=right-left+1;
               }
           }
       }
       return s.substr(begin,maxlength);
    }
};

3.思路分析

---

这里是引用

引用原文：

`
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/by-dodo_1202-k031/
、