Leetcode 3474

Link: https://leetcode.cn/problems/longest-palindromic-subsequence-after-at-most-k-operations/

题目要求

给你一个字符串 s 和一个整数 k。
在一次操作中，你可以将任意位置的字符替换为字母表中相邻的字符（字母表是循环的，即 'z' 的下一个字母是 'a'）。
返回在进行最多 k 次操作后，s 的 最长回文子序列 的长度。

核心算法和原理

区间DP，dp[m][i][j] 表示在操作次数至多为m的情况下，s[i..j]的最长回文子序列长度

选或不选（是否将s[i]或s[j]加入回文的子序列中）：

不选s[i]或s[j]则为 dp[m][i + 1][j] or dp[m][i][j - 1]
选：设最优地进行op次操作后s[i] = s[j]，res = | s[i] - s[j] |，op = min(res, 26 - res)，则为dp[m - op][i + 1][j - 1]

代码


class Solution {
public:
    int longestPalindromicSubsequence(string s, int k) {
        int n = s.size();
        vector dp(k + 1, vector(n, vector<int>(n)));
        for (int m = 0; m <= k; m++) {
            for (int i = n - 1; i >= 0; i--) {
                dp[m][i][i] = 1;

                for (int j = i + 1; j < n; j++) {
                    int dif = abs(s[i] - s[j]);
                    int op = min(dif, 26 - dif);
                    dp[m][i][j] = max(dp[m][i + 1][j], dp[m][i][j - 1]);
                    if (m - op >= 0) {
                        dp[m][i][j] = max(dp[m][i][j], dp[m - op][i + 1][j - 1] + 2);
                    }
                }
            }
        }
        return dp[k][0][n - 1];
    }
};