当前位置：首页 > news >正文

【算法日记】Day 4 一维动态规划基础（按字符DP）

news 2026/7/23 13:32:04

Abstract：#动态规划#一维DP#子序列#按字符DP

1. 题目

题目：LeetCode 940：不同的子序列 II
核心思路：用all记录当前所有不同的子序列总数（包含空串），cnt[26]记录以每个字母结尾的子序列个数。每遍历一个字符ch，新增的子序列数curNew = all - cnt[ch]（即之前所有子序列后面加上ch，再减去已经以ch结尾的重复部分）。然后更新all和cnt[ch]。最后返回all - 1（去掉空串）。
复杂度：时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( 26 ) = O ( 1 ) O(26) = O(1)O(26)=O(1)。

2. 代码

classSolution{public:constintMOD=1000000007;intdistinctSubseqII(string s){vector<int>cnt(26,0);// 按字符DP：以每个字母结尾的不同子序列个数intall=1;// 所有不同子序列总数（包括空串）for(charch:s){intidx=ch-'a';intnewSeq=(all-cnt[idx]+MOD)%MOD;// 严格新增的子序列数all=(all+newSeq)%MOD;cnt[idx]=(cnt[idx]+newSeq)%MOD;}return(all-1+MOD)%MOD;// 去掉空串}};

3. 心得

状态转移选择：这道题一反常规，不以位置为转移状态，而是以字符为视角。如果坚持按位置 DP（比如 dp[i] 表示前 i 个字符的不同子序列数），去重会非常困难。注意到每一轮的重复子序列事实上仅依赖于当前字母，因此从字符角度记录以每个字母结尾的子序列个数才是关键，这样一来就能在再次遍历到某一字母时能够直接从上一次遇到该字母时的情况得出当前轮会有多少重复子串。
核心逻辑：做题时自己已经想到了以当前字符结尾的子序列是在上一轮已有子串基础上生成的，但这种仅从位置角度考虑状态转移的思路只能得出未去重的子序列数，阻塞了解题思路。结合字符角度的状态转移思考，不难得出去重思路——当前轮严格新增子序列数 = 所有已有子序列（包括空串）后面拼接当前字符减去之前已经以该字符结尾的子序列数。再用新增子序列数更新所有已有子序列数和以该字符结尾的子序列数。
空串处理：all初始为 1（代表空串），最后返回all - 1去掉空串。容易忘记取模导致负数，正确写法(all - 1 + MOD) % MOD。
取模的坑：加减法取模将结果限制在[ 0 , M O D ] [0, MOD][0,MOD]范围内。