一、7.11周一
1、II,就是微软问过,怎么思考
(1)拆成链,不行
(2)three path,也不行,就是两边的路不一定重复
(3)答案:因为就是环形的话,相较于正常的dp,只会影响最后一个元素的选择, 因为最后一个数的选择要考虑第一个数是否选择,所以就是分两种情况,其他的都是正常递推的✅ 环装,对于正常的dp来说只有最后一个会受到影响,其他都是不变的
(4)✅ 环的题目,就是一个元素的环需要特殊处理,环的corncase
二、7.12 周二
要对house robber的母题的处理方法特别熟悉,就是想到了就能就是瞬间想出来思路f[n][1]的状态定义,记住就行了
然后就是互不相关的可以分别处理,这是kickstart D轮的题目的总结
三、7.13 周三
1、❎ 自己思考的是二维dp,就是状态转移有问题
又是10^4,必然是KN复杂度
相等也是整除的一种,就是相等就是j / i = k
状态转移方程可能有点问题
思考了1.5h
2、三维DP✅ 按照循环来定义dp的状态
读题:对条件的翻译就是,就是不能间隔一个相等,
Dp的处理方法:这样就是多定义一个维度,就是记录连续的三个数字,这是dp+三个位置的方法❌ 不是滑动窗口⭕ 自己是先一维度dp,然后二维dp,结果答案是三维dp,适应就行了
(1)双周赛第四题
(2)一看就是dp,就是没有其他的任何算法会让你去取mod的,因为是数量的,就是这是一个标志 + 10^4的复杂度,必然是三维状态,就是n * 6 * 6✅ 就是根据时间复杂度反推状态定义是三维的
(2)怎么初始化,就是对于前两个位置⚠️ 考虑实际的意义,忽略状态的定义和转移✅ 相当于递推的初始化的条件,就是直接考虑实际意义,这个也是y总的经验,很重要的经验
(3)对于gcd(a,b) == 1,并不是全部包含a != b的情况,也就是这两个条件要显式的写出来,因为有a == b == 1的情况✅ 这个是gcd的细节
四、7.14 周四 robber II
五、7.15 周五
比robber II多了一个任意起点 + 长度要求
(0)robber II是母题
(1)❎ 遍历每个起点,做一遍dp⚠️ robberII是不需要任意起点,直接从
(2)添加一维长度
方法一:
看错题目了:你是每次都是随意取
拆环成链
方法二:✅
关键是题目条件的转换,转换成robber II的题目的条件 + 这个题目多的条件✅ 这是新的题目出题的方法 = 把母题的条件就是用其他的等价方式说出来(这一步需要就是通过母题专题训练来训练,熟悉之后才能解除基础部分) + 添加新的限制条件(临场推导,就是考察你对母题的推导过程的熟悉)✨总结:这两个步骤是有先后关系,所以就是先要训练透彻第一个能力,才有机会解除第二个能力 -> 需要一步一步来,先通过母题专题训练就是让自己能够在新题或者应用题中看出来需要用的母题,转化成旧题目的能力是非常重要的,也是低级别的比赛里面重点需要训练的能力或者说基础题的部分的分数
Robber II里面不用拆环成链,这是比较特殊的一种环的题目,就是直接拆成单链,然后对首尾进行特殊讨论就行了
Dp,长度
LTE了,就是三维dp的方法是正确的,有进步
(0)直接从第一个点讨论就行了,不用每个点遍历一遍因为本来就是中间会有选或者不选,就是在从第一个点开始的方案里面已经包含了 + 最后返回的答案是直接f n cnt这是robberii的一个精髓⭕ 关键需要对母题就是很熟悉
(1)robberII其实也是没有规定起点,所以就是robberII的解法是线性的,不用遍历起点✅ 就是还是需要对robberII足够熟悉,就是还是需要弄透彻robberII
(2)转化的方法:把robberII 转化为两个robberI的子函数,因为就是robber II转化为I的时候,本质就是两种情况:robberI(1,n-1),robberI(0.n - 2)就是转化为两个robberI的子问题✅ 这个转化非常巧妙,就是你接下来只要专注思考robberI这个子问题就行了
六、7.16周六
298场周赛,第四题
一、读题错误:不是填格子
我的方法:超时 + 不可行
1、maximum必然是dp
2、选prices必然有些贪心,单位价格大的
⚠️ 好像在提高课里面见过,就是很类似的条件
二、答案:关键就是entire切一刀 + 状态定义是按照长宽来定义
题目意思:每次切割都会把已经有的矩形变成单独的两个矩形,然后挑其中的一个矩形再进行切割,另一个矩形直接丢弃❎ 不是用piece去填矩形✅ dp,就是每次切一刀都是entire两个小的矩形,就是状态转移,每个矩形的状态,由两个子矩形的状态来转移✨总结:关键是读题,就是这一道是entire长或者宽,就是分成两个单独的矩形
(1)枚举砍一刀的方法,就是最多200种,横向、竖向单独枚举
(2)✅ 这里这个砍一刀就是明显的一个状态划分的过程,就是entire一刀之后,两边的矩形就是完全没有关系了,就是完全的两个独立的子状态,这个和动态规划是完全一样的,就是非常明显的dp,转移到子状态
Dp:
状态定义f[I][j]表示长为i,宽为j的矩形的最大价值✅ 直接用长宽来定义状态,而不是坐标,因为我们只需要看长宽固定的矩形的最大收益
七、7.17周日
1、相邻的不同,robber,思考如何转换
2、定义状态是:最后一个数选或者不选❎ 不是最后一个数是什么✅ 因为最后一个数是什么可以通过s[i]访问得到,不用记录,对于i - 1也是一样,可以直接访问得到✨总结:一般这种不能相邻的,状态定义是最后一个数选或者不选
① 序列dp的状态定义,必然是就是以i结尾
3、这里题目要求,就是还是要记录尾数,因为是需要判断当前的和过去的之间的比较,不能相同,不是比较原本序列里面相同的两个,而是选出来的序列中相邻的两个
① 特殊的情况就是直接按照实际意义初始化,比如长度等于0的,尾数没有数字,那就直接是一种方案,按照实际意义来赋值
⚠️ 不可能TLE✅ 就是f初始化太多了,学会typedef longl long LL在最上面;然后LL f[N][N][2]在中间,就是这是LL的数据定义用的方法
答案:
套路dp题,真的太猛了,确实是常规题
八、7.18周一⚠️ 自己写出来的,y总都讲过
1、判断有效括号:
任何子序列左括号大于右边括号,l >= r
左括号和右括号相等
2、玉米地
初始化过的值,就是不用再进入状态转移了
⚠️ 检查清楚状态转移的方程是否写对了
九、7.19周二
1、周赛第三题,明显的dp题,关键是题意的转换,就是转换成区间里面出生的点的个数✅ 常用的套路固定住之后,思维还是不难的,关键就是要笃定是这种套路,这个需要就是多做题,多专题训练,这样竞赛的时候随机训练才能笃定
十、7.21周四 301周赛第四题
十一、7.22周五 ca题,非常简单的ca题
十二、7.23周六 ca题
构造题,就是和昨天完全一样,就是分情况证明,在ca里面算简单的
✅ 我适应了ca构造题的难度之后,这种lc的构造题真的是特别简单,特别特别简单的,就是真的是分析一会就直接出来的那种✅ 体会到了就是天天打cf的人,就是真的是玩lc真的是切菜一样,真的是降维打击
十三、7.25周一
1、T358✨
✅ 还是有很多细节的,就是最后长度没有k的处理,很重要的一个trick + 优先队列的, 取出来丢进去,这是最normal的处理方式
⚠️ 直接在T767里面写题目
⚠️ T767的general的题目,就是用优先队列,每次取频次最高的两个数字,然后更新之后再丢进去✅ 这样可以处理k个的情况
(1)取k个的话,k个字母不能相同,就是题目转换
(2)优先取频次多的,这样就是尽量就是两段之间必然是不会有k个位置之内重复的
代码:
(1)优先队列是特殊的,就是频次大的放在前面
(3)⚠️ 优先队列里面的个数[HTML_REMOVED]0的时候才能加入
(1)加了一个空元素填充,就是在弹出前k个元素的时候,不够就用空元素填充就行了
1、只要数量
不能直接算数量,因为就是中间的元素可能就是会重复,还是要模拟过程
2、具体方案
(1)就是长度一直是k,对于多出来的空格,最后直接删除就行了,因为中间的长度也要保持是k
(2)代码:就是PIC里面的{int,char}顺序搞反了
⚠️ 手写堆 + 自定义数据类型的手写堆✅ 一样的,就是比较的时候只比较第一个维度就行了
十五、7.28周四
T984
我的方法:
构造题,就是必然这种构造方式是可行的✅ cfca构造题的训练,对于这种贪心题的训练就是真的有很大的帮助
答案:
一、可以直接贪心构造,就是思维难度比较大,然后扩展性比较差
二、把{频次,char}放在堆里面,然后按照套路化的方式取出来✅ 这种方法是可以举一反三的
(1)只有两个字母,所以就是判断两个字母之间的数量关系,只要堆顶的个数 > 堆的第二个字符的个数,那我就aab这样;一旦相等,我们就是ababab直到技术✅ 本质还是优先队列公式的改编
十六:7.29周五
7.29周五 T1405
⚠️ 从两个xxx扩展到三个xxx + 从必然x个扩展到最多x个
⚠️ aaa、bbb的模板公式:cnt(a) > cnt(b)的时候就是aab;cnt(a) == cnt(b)的时候就是ab✅ 这个贪心的思路是处理k = 3然后就是可以aab的这种题目的公式,就是这个公式的拓展
⚠️ 优先队列真的是非常有用,就是多路归并,然后arrange k stride,公式都是用优先队列
十七:8.1周一
【每日lc打卡】
T2333
⚠️ 母题:让数组里面的数尽量平均
1、map的解法,每次让最大值减少1,就是对于k非常大的时候
(1)因为k太大了,这里每次需要让最大值的所有个数 - 1,记录每个数值的个数
(2)⚠️ 又考到了map✅ 就是map[HTML_REMOVED],然后插入元素是mp[val];然后
T2234
答案:
(1)就是根据公式是一个加法,就是最朴素的就是:把两个部分就是尽量都达到最大值,这是加法公式最朴素的想法
(2)代码:二分
① 前缀和从0开始的话,就是sum[0] = a[0]
我的想法:
平均主义的母题
(1)k很大,就是T2333的版本
达到target之后就踢出去,然后就是增加下一个值
代码:
(1)map[HTML_REMOVED] hp;就是map本来就就⚠️ 又考察到了map
十八:8.2周二
T2350
构造题,就是小学奥数题
(0)先从最简单的情况分析,就是从长度k = 1的情况分析
① K = 1的时候,找到就是一个区间是让每个元素至少出现一次的最短的区间长度,并且!区间的最后一个元素x必然是在区间里面只出现了一次;
② 然后你要去构k = 2的时候,其实是只要需要考虑x * 的情况就行了,因为就是只要能够满足x *的所有情况,那必然能够满足所有长度为2的请款,所以就是再找到一个区间就是每个元素只出现一次,并且!区间的最后一个元素是y,
③ 以此类推
(1)找subsequence就是更容易,找subarray就是条件太限制了
十九:8.3周三
T2242
路径长度 = 3,四个点
无环
一条路径上的点依次
方法一:以点为单位
(1)确定起点:❎ 度最多的点
(2)
方法2:以边为单位,任取三条边,这种形式
✅ 这种 = 4的,就是必然是一种特定的构造方法,就是类似前面的palindrome中len = 3,必然是贪心的构造方法
(1)x y z k
(2)以中间这条边进行遍历,然后从x的邻接点,y的邻接点去选,这样必然是符合要求的,o(n)
(3)bool邻接表存,邻接矩阵存不下来
(4)贪心:
① 找x、y的最大的邻居 -> 存在的问题:可能就是x的最大邻居是y,或者最大的邻居和y的最大的邻居相同
② 找x、y的前三个大的邻居,就是遍历
(5)代码:
① lc里面的邻接表,就是用vector[HTML_REMOVED] ne[N],就是邻接表,就是lc里面的邻接表的定义✅ 就是lc的特定的方式,而且写起来更好写,虽然性能慢一点,但是在lc里面就是够用了 + 这个题目是必须要用这个
② y总的定义方法是以边为单位,就是idx表示的是一条边,因为一般是边权✅ 可以看成边,也可以看成点上的权值,都行了,可以把所有的邻接点的放在边权上,然后起点放在自己ide点上
8.4周四
T2332
⚠️ 数组的题目,大概率是贪心,或者构造题✅ 切入点就是思维的切入点很重要的,否则就是思考会不清楚
我的思路:以人来考虑
方法一:从后往前考虑,只考虑最后一辆车,就是没法考虑因为前面留下的人会影响后面的人
方法二:要确定最后一个坐车的人的位置,就是装车,前面的车会影响后面的车
答案:以每辆车从前往后来讨论,代码描述思维的能力
(0)⚠️ 因为就是给出的数据来看,就是每个车装什么人都已经确定了,那我只要每个车判断一下我最晚上这辆车的时间就行了✅ 对于每辆车就是有一个细节就是:不能和其他人的时间相同,这是上车的唯一的限制✨找到确定的东西,然后就是在这个确定的东西上去完成
(1)车满了,就挤掉其中一个人
① 假设车全部满了,而且就是占满了每辆车的所有的时间,那上不了车?就是等于第一辆车的上车的最大值 = 1
(2)车没满,就卡点上车
代码:
(1)对于每个上车的乘客,我们都求一遍结果,这样对于每个上车的人都求过了,必然是全局的最晚的值
8.5周五
T2311
(1)字符串hash只能判断两个字符串是否相同,就是不能用来判断字符串是否等于某个值,因为就是实际上是对字符串做了hash值的变换⚠️ 而且也不能比较大小,因为就是做了%ULL的运算
(2)⚠️ o(1)时间判断一个二进制串是否就是<=十进制值
0️⃣ 方法:十进制转二进制,然后保证两个二进制串长度相同,然后直接字符串比较
① 转换成二进制进行比较,直接进行字符串的比较,就是字符串的比较
② “100101” > “101” = false,因为是从前面开始比较✅ 先保证就是长度一样,高位补0,这样就可以直接比较了
代码
(1)就是一个一个走,没走一次就是一次循环,这样比较好思考,就是代码比较好写
(2)k是定值,就是只要转换一次就行了
8.6周六
T2236
背景:
(1)经典的算法题,题目越是简洁,说明就是越是经典
(2)✅ 数据范围如果对于a[i]的值有限制,就是限制到一个小的范围,比如1000,那大概率是dp,而且是状态定义和数值有关
(3)因为对于a[i]只有两种操作,这也是符合dp的扩展的,就是只有两种扩展方式
方法一:DP
(1)lc因为对于数值有限制,就是可以用dp
方法二:贪心
(0)非常固定的解法,就是只能用在这一道题目
(1)和数值没有关系,
8.7周日
T2360
基环树
(1)对于找环,就是每个点只要遍历一遍就行了
(2)✅ 关键的性质就是:
① 对于一个点,如果遍历过,那必然就是已经找过了经过这个点的环;
② 如果是当前这条路径遍历的,那就是找到了当前路径的环;否则就是直接break
8.9周二
T2127
基环树,最大环的应用
(0)基环树找最长链,可以用topsort,就是从入度为0的点开始剥掉,最后剩下的点必然在环里面
(1)这里一个人必然有一个喜欢的人,那说明就是一个点必然有一个出度,就是比基环树的定义还要更加严格,基环树的有些点是出度是0
(2)必然有一个出度,但是可以有任意个入度
题目:
(1)一种特殊情况,两个人相互喜欢,二元环是特殊情况,题目里面说明了这种情况,就是可以连接外面的链✅ 只有两个人成的环是可以这样的
(2)这里第一个样例就是特殊情况,就是有点迷惑人,就是后面两个才是正常的情况✅ lc的样例,一般会把特殊的例子放在样例里面,这是比较好的一个地方,就是要注意他会就是放在第一个,就是首先就是让你考虑特例,这样你就会本能的第一反应就是考虑特殊的样例,就是会考虑复杂
8.10周三
T792
✨ 非常好的一个题目,就是锻炼自己对于暴力解法优化的思考过程
(1)找子序列的公式题,就是o(子串.size())的公式题目,掌握了一个新的母题
(2)预处理next[I][char]的方法是最优的
0、✅ 基础 = 暴力解法 = 判断是不是subsequence,双指针 + 本质是贪心思想(找母串最前面的匹配的字符,这个是后面两种优化方法的基础)
(1)有点类似构造题,就是需要换角度去遍历
1、状态机
(1)知道子串的字符char,要快速找到母串中的第一个char的位置,这里直接用o(1)找到
(2)状态定义:next[0][char]表示从0开始往右看,就是找到母串s中的第一个char
① 更新的方法:从后往前处理,就是因为next[7][char]其实只与next[8][char]复制一遍 + 根据s[8]的值,修改一个next[7][s[8]]就行了
(3)代码
① ✅ int next[n][26];对于二维数组,如果有一维是10^5级别,就是最好就是用数组,绝对不要用vector,就是vector在lc里面就是二维数组的时候效率非常低,很可能就是会TLE
2、二分
(0)二分优化暴力求解的一部分,这是常规优化方法✅ 关键还是只有26个字符,找到char最近的位置
(1)通过二分快速找到第一个匹配当前b[j]的a[i]的位置
(2)代码:直接用一个变量i记录当前在母串中遍历到的位置,因为必然是递增的,所以就是对于posiont[char - ‘a’]虽然前面有找到过的的,但是也必然不会重复找,因为i必然已经增加了,所以就是不用管axxxa就是怕第二个a会和第一个a重复
3、我的想法:字符串hash
⚠️ 如果是是判断是否是子串,那可以用字符串hash
(1)字符串hash可以求出一个字符串所有子序列的hash值?o(n^2),退化了,没有必要
T524
找到集合里面的最长子串,上面的公式题的应用
(1)这个题目的数据范围,❎ 用二分更加的优化✅ 二分的话,是o(n^2logn)
8.11周四
T2055
每次query都要达到o(1)或者o(logn)✅ 预处理,直接就是o(1)算出来
推导出来计算公式
8.12 周五
T1055
(0)✅ 对遍历对象的一个转换,就是从target的角度去思考遍历的方法,因为target在题目要求是需要连续的,所以就是判断当前target的这个子串,在source中能够找到的对应的最长子序列
(0)这种状态机的方法,是找子串,扩展性最高的方法
(0)每次找最长子串,贪心下来就是数量最少
(1)当前子串在遍历的时候,如果找不到的时候,就是要判断一下当前子串分割出来的长度,如果长度 == 0,说明就是分割失败;否则cnt
答案:
(1)有两种情况的出来答案✅ 对于遍历结束的情况,实际上可以用一个哨兵来判断边界
① 当前target字符串中的char在source中找不到✅ 找不到的时候,必然是j = 0,因为就是前面只要有能够找到的,我们找到-1,就是会单独拿出来成一个串,所以就是会回到j = 0,所以就是找不到的情况必然就是j = 0,就可以少用一个flag标志
② 当前target字符串找完了
8.13周六
T727
✅ 找子序列的这个状态机的方法,是最具有扩展性的,就是只要掌握这种方法,找子序列就都可以用这种方法,这就是母题专题训练的作用
(0)只要是判断一个字符串,在一个母串里面是子序列的情况,就是用这种状态机的方法,可扩展性是最高的
(1)就是针对只有小写字母的26种情况,常数级别的情况
arrange w k stride
题目合集
1405、984、621、358、1054、、2335、1953、767
类型
k = 2,ab
k = 3,aab
先贪心aab,然后转化成ab
k = k,aaaab
也是一样,先贪心,转化成其中的一种ki
【7.4周一-7.10周日】
知识点:二分、最短路、maximum subarray专题(五题)
0️⃣、7.4周一 2302-看题解
然后时间复杂度必然要求nlogn
一段区间,必然是前缀和;推导公式可以知道,当一段区间符合要求的时候,里面的子区间必然符合要求,这就是二分
(1)固定左端点;然后二分右端点,子区间的个数 = j - i + 1
一、7.5周二 1631-看题解
复习单元最短路径的板子
1、❎ dfs,没有需要找具体方案
贪心总是找最小的方向,没办法保证全局最小,复杂度太高而
2、❎ dp✅ 最短路的方法,就是类似的
方向有上下左右,更新不全,dp的方向没法更新
3、最短路模板
完全的最短路的模板,主要是构造图,就是题目条件是构造边
(1)这里的话,是表示从1->(i,j)路径上的最大的差的绝对值,然后和当前的这条边的绝对值相比,就是更新后面的点
边最多是10000,点最多是10000
(1)朴素版本n^2超时
(2)堆优化版本
邻接矩阵存储就是会超过,在acwing最好用邻接表,lc用邻接矩阵是可以的
二、7.6周三 53-自己想的
母题,就是dp的题目,dp的解法是扩展性最高的
滑动窗口板子题
(1)就是200题里面见过,就是当产生负数的时候,直接sum = 0,因为必然是最后一个数字导致产生负数的,然后整个区间在后面都是不能用的✅ 对于滑动窗口的一个优化
三、7.7周四 2321-0.5自己想的 + 0,5看题解
1、对于数学证明,就是自己的推导错了一个性质,所以就是缩小了答案的范围,然后出错了✅ 数学分析的时候一定要谨慎,就是只有能够证明出来的结论才是真的能够用的,因为证明出来的数学的性质是缩小答案的范围,从而考虑的情况变少了,如果数学性质就是推导错误了,就是会漏掉一些情✨总结:数学分析的时候一定要严谨,就是只有完全万无一失的时候才能用,否则就是多考虑一种情况,就是代码里面多考虑一种情况就行了,这是数学推导性质的经验
(0)对于推导出来的数学结论,通过20s的找反例去验证,就是找不出反例就是自己做到了极致
(1)这种困难的时候,都是自己进步的时候,一定要明白就是自己的进步,就是这种时候的总结,就是失败之后总结的时候才是进步的时候,一定要清楚,就是痛苦才是进步的源泉
2、如果不是连续的区间和,就是子序列的话,就是用dp来求✅ 连续的也可以,就是状态表示不同,就是subarray的经典解法
四、7.8周五 1186-看题解
1、❎ 自己ide思路:三种想出来的思路都是不对的,虽然代码都实现出来了✅ 因为自己的基础题的算法不对,就是没有用dp,太麻烦了
❎ 只要是负数就要跳过,而不是sum < 0才跳过,因为会减少和,后面再出现负数,就这段就是没有用处了
和为负数的时候才需要跳过,就是跳过当前的这段,当和不为负数的时候再继续,因为必然是最后一个加进来的数导致成为了负数,这里充分了用了这个性质,才能够解题✅ 适应通过i的滑动窗口来调整
(1)充分了用sum < 0这个性质,就是必然是前面这一段完全都不需要了
(2)滑动窗口部分不变✅ 关键是这个消掉的负数的处理,这个是关键
(3)要有一个特殊处理,就是开头必须要是正数,否则会浪费消掉负数的机会
2、题解的思路:最简单的情况的dp解法
(1)最基础的解法:f[i]表示包含a[i]的最大的连续子数组的和,也是可以用dp的⚠️ 写一遍,dp写法,连续和不连续都能写
(2)有一次操作的机会,这样就是状态表示上需要多一维
五、7.9周六 152-自己做出来的(做过的)
1、本能的思想:f表示正数的最大值;g表示负数的最小值⚠️ 这样就是分符号,就是处理起来比较麻烦
保证子串非空,那就是状态初始化要初始化成当前元素a[i],就是只包含当前元素的状态
2、答案的思路:f表示最大值,g表示最小值,然后更新最大值、最小值的时候,无脑就是算出来结果,然后max或者min就行了,不管是正负,只要管f是最大值,g是最小值就行了✅ 直接记录最大和最小值就行了,因为题目要求的是求最大值,不管正负,所以就是用一个状态记录最大值,一个状态记录最小值
六、7.10周日 2272-看题解
1、我的思路:dp、滑动窗口,都是会进入死胡同,就是题主也是当场没有想出来
2、答案:
(1)一般n^3是开到10^3;然后nlogn是开到10^5,所以就是10^4是非常奇怪的复杂度;所以就是如果10^4的复杂度的话,就是o(kN),然后就是k是100的级别,从而找到突破口
26^2,就是把字符两两配对,然后就是去找这个字符串里面的这两个字符的个数的差
(2)然后这个题目就是有一个难点:
就是全部找到1111,是符合最大值,但是这种按照varience定义是0,所以就是必须包含一个-1进来
为了必须包含一个-1,就是求一个-1结尾的,然后-1开头的,然后就是对于nums[i] = -1的地方,就是dp1[i] + dp2[i] - nums[i]就是必然包含nums[i] = -1的最大的和✅ three path,就是左边一遍,右边一遍,然后按中间这个需要包含元素为基准过一遍
① 没有不存在-1的情况,因为就是样例保证必然有两个不同的字符;在判断的时候,就是只判断字符不相等的情况,也就是必然有1和-1
② 就是样例没有“aaaa”这种吗✅ 对于这种样例,直接就是res = 0,就是不处理,刚好就是res = 0的初始化
③ 对于就是只包含小写字母的这种,就是可以遍历26种可能性,就是这是可以突破的地方,暴力枚举
(3)写代码:就是对于这种双向分别dp的,就是第二个dp最好就是用变量来记录,这样可以节约一次;否则就是在这个题目会卡住