做网站有哪些行业,wordpress落地页模板,html网页代码大全移动字体,上海最新发布最新2024.6.8 **每日一题**
3040.相同分数的最大操作数目 Ⅱ#xff0c;通多题意可知#xff0c;该题最多有三种操作分数#xff0c;分别是前两个#xff0c;最后两个#xff0c;以及第一个和最后一个的和。从这里也可以看出一共有三种状态转移方式#xff0c;所以我们可以利…2024.6.8 **每日一题**
3040.相同分数的最大操作数目 Ⅱ通多题意可知该题最多有三种操作分数分别是前两个最后两个以及第一个和最后一个的和。从这里也可以看出一共有三种状态转移方式所以我们可以利用DP或者记忆化搜索的方式来求解。对三种操作分数分别求最大次数再求他们的最大值。依次判断三个状态当前区间的前面两个最后两个以及第一个和最后一个直到遍历区间长度为1就可以求出整个区间的答案。 516.最长回文子序列该题是一个区间求最值问题我们自然地想到可以通过小区间转移到大区间来进行求解状态转移就对应着动态规划或者搜索算法。在本题中我们使用DP思想从尾部开始遍历字符串对于每个字符再遍历它之后的元素一共有三种状态当ij时令数组为1;当s[i]s[j]时我们还要分情况讨论如果ij-1此时直接令数组为2因为下一个状态ij;如果ij-1那么f[i][j]f[i1][j-1]2;
最后一种情况是当两个字符不构成回文子串时我们选择上一个状态下最大的一端继续前进
f[i][j]max(f[i1][j],f[i][j-1]);
