力扣 2370. 最长理想子序列

题目来源：https://leetcode.cn/problems/longest-ideal-subsequence/

大致题意：
给一个字符串和整数 k，求出给定字符串的最长理想子序列

理想字符串的定义如下：

• 字符串每相邻两个字符的绝对差值小于等于 k

思路

该题与最长上升子序列类似，不过上升子序列是要求子序列中按照递增顺序，该题是相邻字符的差值小于 k

于是可以使用动态规划解题，使用 dp[i] 表示以字符 s[i] 结尾的最长理想子序列长度

那么状态转移方程为：

• dp[i] = dp[j] + 1，其中 s[i] 与 s[j] 的绝对值差小于等于 k

这里可以发现，与 dp[i] 有关的状态，仅仅是与 s[i] 绝对值差小于等于 k 的字符，而与 j 具体的值无关，简单地说

• 设当前有 j1 和 j2，其中 j1 小于 j2，那么最终对 dp[i] 有贡献的值只可能是 dp[j2]，因为在更新 dp[j2] 的时候已经考虑过 dp[j1]，也就是 dp[j2] 的值一定大于 dp[j1]

所以这里可以使用数组优化，仅仅使用常数大小的数组 dp[26] 表示截至当前遍历位置的以每种字符结尾的最长理想子序列长度，具体更新时规则为

1. 设当前遍历位置为 i，字符为 s[i] ，那么对 dp[i] 有贡献的字符范围为 [s[i] - k, s[i] + k]（ 也就是若当前字符为 s[i]，那么以当前字符结尾的最长理想子序列的前一个字符最小是 s[i] - k，最大是 s[i] + k）
2. 遍历这个字符范围，dp[i] 即为该范围中的最长理想子序列长度 + 1

具体看代码：

	public int longestIdealString(String s, int k) {
        int n = s.length();
        int[] dp = new int[26];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 获取当前字符在数组中的索引
            int idx = s.charAt(i) - 'a';
            // 获取前一个字符允许出现的范围，这里注意不能越界
            int left = Math.max(idx - k, 0);
            int right = Math.min(idx + k, 25);
            int cur = 0;
            // 获取以当前字符结尾的最长理想子序列长度
            for (int j = left; j <= right; j++) {
                cur = Math.max(cur, dp[j] + 1);
            }
            // 更新以当前字符结尾的最长理想子序列长度
            dp[idx] = cur;
            // 更新最长理想子序列长度
            ans = Math.max(ans, cur);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22