当前位置:网站首页>力扣刷题记录
力扣刷题记录
2022-07-06 09:25:00 【爱学习的小耿】
动态规划
第一例 最长回文子串的问题分析和解题思路
文章目录
前言
提示:这里可以添加本文要记录的大概内容:
本人新手,写博客纯属自我记忆,方便回顾,不喜勿喷
提示:以下是本篇文章正文内容,下面案例可供参考
一、动态规划是什么?
就是直接从最底下,最简单,问题规模最小的 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/
、
边栏推荐
- 软件测试有哪些常用的SQL语句?
- Should wildcard import be avoided- Should wildcard import be avoided?
- LeetCode#198. raid homes and plunder houses
- Cadence physical library lef file syntax learning [continuous update]
- Want to change jobs? Do you know the seven skills you need to master in the interview software test
- LeetCode#2062. Count vowel substrings in strings
- Stm32 dossiers d'apprentissage: saisie des applications
- ucore lab 6
- Leetcode notes - dynamic planning -day7
- 学习记录:使用STM32F1看门狗
猜你喜欢
ucore lab 2
学习记录:理解 SysTick系统定时器,编写延时函数
转行软件测试必需要知道的知识
Learning record: USART serial communication
Crawler series of learning while tapping (3): URL de duplication strategy and Implementation
How to do agile testing in automated testing?
Interview answering skills for software testing
软件测试工作太忙没时间学习怎么办?
学习记录:TIM—基本定时器
Lab 8 file system
随机推荐
Do you know the advantages and disadvantages of several open source automated testing frameworks?
Cadence physical library lef file syntax learning [continuous update]
Currently, mysql5.6 is used. Which version would you like to upgrade to?
LeetCode#53. Maximum subarray sum
The latest query tracks the express logistics and analyzes the method of delivery timeliness
学习记录:STM32F103 时钟系统概述工作原理
[C language] twenty two steps to understand the function stack frame (pressing the stack, passing parameters, returning, bouncing the stack)
JS --- all basic knowledge of JS (I)
Eigen User Guide (Introduction)
LeetCode#412. Fizz Buzz
Example 071 simulates a vending machine, designs a program of the vending machine, runs the program, prompts the user, enters the options to be selected, and prompts the selected content after the use
Intensive learning notes: Sutton book Chapter III exercise explanation (ex17~ex29)
C4D quick start tutorial - creating models
学习记录:USART—串口通讯
UCORE LaB6 scheduler experiment report
JDBC介绍
Introduction to variable parameters
How to rename multiple folders and add unified new content to folder names
Do you know the performance testing terms to be asked in the software testing interview?
Research Report on medical toilet industry - market status analysis and development prospect forecast