2024.6.8

2024.6.8

**每日一题**

3040.相同分数的最大操作数目 Ⅱ，通多题意可知，该题最多有三种操作分数，分别是前两个，最后两个，以及第一个和最后一个的和。从这里也可以看出一共有三种状态转移方式，所以我们可以利用DP或者记忆化搜索的方式来求解。对三种操作分数分别求最大次数，再求他们的最大值。依次判断三个状态，当前区间的前面两个，最后两个，以及第一个和最后一个，直到遍历区间长度为1就可以求出整个区间的答案。

516.最长回文子序列，该题是一个区间求最值问题，我们自然地想到可以通过小区间转移到大区间来进行求解，状态转移就对应着动态规划或者搜索算法。在本题中我们使用DP思想，从尾部开始遍历字符串，对于每个字符再遍历它之后的元素，一共有三种状态，当i==j时，令数组为1;当s[i]==s[j]时，我们还要分情况讨论，如果i==j-1，此时直接令数组为2，因为下一个状态i>j;如果i！=j-1，那么f[i][j]=f[i+1][j-1]+2;

最后一种情况是，当两个字符不构成回文子串时，我们选择上一个状态下最大的一端继续前进，  

f[i][j]=max(f[i+1][j],f[i][j-1]);