题目

迪沃斯定理

题目链接

解题思路（最少划分上升子序列问题 · 四个动态规划解法）

问题拆解

给定一个长度为 n 的整数序列，要求输出以下四行结果：

最长严格上升子序列的长度；
将序列划分为若干个严格上升子序列所需的最少个数；
最长非严格上升（即不下降）子序列的长度；
将序列划分为若干个非严格上升子序列所需的最少个数。

其中第 1、3 问是经典 LIS 变种，而第 2、4 问的关键在于理解：

最少划分数 = 最大“冲突组”的大小。
所谓“冲突”，是指两个元素无法出现在同一个目标子序列中。

核心观察：冲突与划分下界

对于严格上升子序列：若存在 i < j 且 a[i] >= a[j]，则 a[i] 与 a[j] 冲突，不能共存。
- 因此，任意一个非递增子序列中的所有元素两两冲突，必须分属不同子序列。
- 故最少划分数 ≥ 最长非递增子序列长度。
同理，对于非严格上升子序列：若 i < j 且 a[i] > a[j]，则冲突。
- 所以最少划分数 ≥ 最长严格递减子序列长度。

因此：

第 2 问答案 = 最长非递增子序列长度；
第 4 问答案 = 最长严格递减子序列长度。

动态规划设计

我们使用四个简单的 O(n^2) DP 分别求解：

问题	DP 含义	转移条件
1. 最长严格上升	`dp1[i]`: 以 `nums[i]` 结尾的最长严格上升子序列长度	`nums[j] < nums[i]`
2. 最长非递增	`dp2[i]`: 以 `nums[i]` 结尾的最长非递增子序列长度	`nums[j] >= nums[i]`
3. 最长非严格上升	`dp3[i]`: 以 `nums[i]` 结尾的最长非严格上升子序列长度	`nums[j] <= nums[i]`
4. 最长严格递减	`dp4[i]`: 以 `nums[i]` 结尾的最长严格递减子序列长度	`nums[j] > nums[i]`

每个 DP 初始化为 1（单个元素构成子序列），通过枚举前面所有位置进行状态转移。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // 1. 最长严格上升子序列: dp1[i] 表示以 nums[i] 结尾的最长严格上升子序列长度
        int[] dp1 = new int[n];
        int ans1 = 0;
        for (int i = 0; i < n; i++) {
            dp1[i] = 1; // 初始化: 每个元素自身构成长度为 1 的子序列
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) { // 严格小于才可接在后面
                    dp1[i] = Math.max(dp1[i], dp1[j] + 1);
                }
            }
            ans1 = Math.max(ans1, dp1[i]); // 实时更新全局最大值
        }

        // 2. 最长非递增子序列: 用于计算最少严格上升划分数
        // 原理: 非递增序列中任意两元素冲突, 必须分到不同严格上升子序列中
        int[] dp2 = new int[n];
        int ans2 = 0;
        for (int i = 0; i < n; i++) {
            dp2[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] >= nums[i]) { // 非递增条件: 前者 >= 后者
                    dp2[i] = Math.max(dp2[i], dp2[j] + 1);
                }
            }
            ans2 = Math.max(ans2, dp2[i]);
        }

        // 3. 最长非严格上升(不下降)子序列: 允许相等
        int[] dp3 = new int[n];
        int ans3 = 0;
        for (int i = 0; i < n; i++) {
            dp3[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i]) { // 非严格上升条件: 前者 <= 后者
                    dp3[i] = Math.max(dp3[i], dp3[j] + 1);
                }
            }
            ans3 = Math.max(ans3, dp3[i]);
        }

        // 4. 最长严格递减子序列: 用于计算最少非严格上升划分数
        // 原理: 严格递减序列中任意两元素冲突, 不能放入同一非严格上升子序列
        int[] dp4 = new int[n];
        int ans4 = 0;
        for (int i = 0; i < n; i++) {
            dp4[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[i]) { // 严格递减条件: 前者 > 后者
                    dp4[i] = Math.max(dp4[i], dp4[j] + 1);
                }
            }
            ans4 = Math.max(ans4, dp4[i]);
        }

        // 输出四行结果
        System.out.println(ans1);
        System.out.println(ans2);
        System.out.println(ans3);
        System.out.println(ans4);
    }
}

接龙数列

题目链接

解题思路(动态规划求最长接龙子序列)

问题转化

题目要求删除最少的数，使得剩余数字按原顺序构成“接龙数列”。
接龙数列定义为：从第二个数开始，每个数的首位数字等于前一个数的末位数字。

由于“最少删除”等价于“最多保留”，问题转化为：

求原序列中最长接龙子序列的长度，答案即为 n - 最长长度。

注意：子序列保持原顺序，但不要求连续。

方法一：朴素DP，适用于小数据

我们使用经典 DP 思路：

状态定义：dp[i] 表示以第 i 个数字结尾的最长接龙子序列的长度。
初始值：每个数字自身可构成长度为 1 的接龙数列，故 dp[i] = 1。
状态转移：对于每个 i，遍历所有 j < i：
- 若 nums[j] 的末位数字 == nums[i] 的首位数字，则可将 nums[i] 接在 nums[j] 后面；
- 此时更新：dp[i] = max(dp[i], dp[j] + 1)。
最终答案：n - max(dp[0..n-1])
该方法时间复杂度为 O(n²)，在 n 较大时会超时。

方法二：状态压缩 DP（O(n)，AC 解法）

观察发现：接龙条件仅依赖于数字的首位和末位，而末位数字只有 0~9 共 10 种可能。

因此，我们可以重新定义 DP 状态：

状态定义：maxLen[d] 表示当前已处理的所有数字中，以末位数字 d 结尾的最长接龙子序列的长度。
初始值：maxLen[0..9] = 0
状态转移：对每个数字 x：
1. 计算其首位 f 和末位 l；
2. 它能接续的最长长度为 maxLen[f]，因此以 x 结尾的最长长度为 maxLen[f] + 1；
3. 更新 maxLen[l] = max(maxLen[l], maxLen[f] + 1)。
最终答案：n - max(maxLen[0..9])

该方法将状态空间从 O(n) 压缩到 O(1)，时间复杂度降至 O(n)，可高效通过大数据。

辅助函数：提取首位与末位

末位数字：x % 10
首位数字：不断除以 10 直到小于 10

该方法适用于正整数（题目保证输入为正整数）。

参考代码

方法一：O(n²)超时无法AC

import java.util.Scanner;

public class Main {
    // 辅助函数: 获取一个正整数的首位数字
    // 通过不断除以 10, 直到只剩一位数
    static int firstDigit(int x) {
        while (x >= 10) x /= 10;
        return x;
    }

    // 辅助函数: 获取一个正整数的末位数字
    static int lastDigit(int x) {
        return x % 10;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // dp[i]: 以 nums[i] 结尾的最长接龙子序列的长度
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 每个数字自身构成长度为 1 的接龙序列
            // 枚举前面所有位置 j, 尝试接龙
            for (int j = 0; j < i; j++) {
                // 如果前一个数的末位等于当前数的首位, 则可以接龙
                if (lastDigit(nums[j]) == firstDigit(nums[i])) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxLength = 0;
        for (int len : dp) {
            maxLength = Math.max(maxLength, len);
        }

        // 最少删除数量 = 总数 - 最长接龙子序列长度
        System.out.println(n - maxLength);
    }
}

方法二：AC代码，换一种 `dp`定义（`maxLen`就是 `dp`数组）

import java.util.Scanner;

public class Main {
    // 辅助函数: 获取一个正整数的首位数字
    // 通过不断除以 10, 直到只剩一位数
    static int firstDigit(int x) {
        while (x >= 10) x /= 10;
        return x;
    }

    // 辅助函数: 获取一个正整数的末位数字
    static int lastDigit(int x) {
        return x % 10;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // maxLen[d]: 当前以末位数字 d 结尾的最长接龙子序列长度
        int[] maxLen = new int[10]; // 初始化为 0
        for (int i = 0; i < n; i++) {
            int first = firstDigit(nums[i]);
            int last = lastDigit(nums[i]);
            // 当前数字能构成的最长接龙长度 = 以 first 开头能接上的最长长度 + 1
            int currentLen = maxLen[first] + 1;
            // 更新以 last 结尾的最大长度
            if (currentLen > maxLen[last]) {
                maxLen[last] = currentLen;
            }
        }

        // 找出所有末位中最大的长度
        int maxLength = 0;
        for (int len : maxLen) {
            maxLength = Math.max(maxLength, len);
        }

        // 最少删除数量 = 总数 - 最长接龙子序列长度
        System.out.println(n - maxLength);
    }
}

松散子序列

题目链接

解题思路(动态规划)

问题理解

给定一个仅包含小写字母的字符串 s，定义其松散子序列为：
从 s 中选出若干字符（保持原有顺序），使得任意两个相邻选中字符在原串中的下标之差 至少为 2（即不能连续或紧邻）。

每个字符 'a' 到 'z' 的价值分别为 1 到 26。
目标是求所有合法松散子序列中，总价值最大的那个。

动态规划设计

状态定义

设 dp[i] 表示：以位置 i 结尾 的松散子序列所能获得的最大价值。

注意：该子序列必须包含 s[i]，且满足松散条件。

状态转移

若 i = 0：只能选自己，dp[0] = value(s[0])
若 i = 1：不能与 i=0 同时选（下标差为 1），所以 dp[1] = value(s[1])
若 i ≥ 2：可以接在任意 j ≤ i-2 的位置之后，因此：
dp[i] = \text{value}(s[i]) + \max_{0 \leq j \leq i-2} dp[j]

优化技巧

直接枚举 j 会导致 O(n^2) 复杂度。观察发现：我们只需要维护一个变量 max，表示 dp[0] 到 dp[i-2] 的最大值。

在计算 dp[i] 时，max 已经包含了所有可接续的位置的最大价值；
计算完 dp[i] 后，将 dp[i-1] 更新进 max，供后续 i+1 使用。

这样，时间复杂度降至 O(n) 。

最终答案

由于最优解不一定以最后一个字符结尾，需取所有 dp[i] 的最大值。

辅助映射

字符 'a' → 1，'b' → 2，…，'z' → 26
可通过 s.charAt(i) - 'a' + 1 快速获取。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();

        // charToValue: 'a'->1, 'b'->2, ..., 'z'->26
        int[] value = new int[26];
        for (int i = 0; i < 26; i++) {
            value[i] = i + 1;
        }

        // dp[i]: 以位置 i 结尾的松散子序列的最大价值
        int[] dp = new int[n];
        int max = 0; // 表示 dp[0] 到 dp[i-2] 的最大值
        int ans = 0;

        for (int i = 0; i < n; i++) {
            int v = value[s.charAt(i) - 'a'];
            if (i == 0) {
                dp[i] = v;
            } else if (i == 1) {
                dp[i] = v; // 不能接在 i=0 上
            } else {
                dp[i] = v + max; // 接在 i-2 或更早
            }
            ans = Math.max(ans, dp[i]);

            // 更新 max: max 是 dp[0] 到 dp[i-2] 的最大值
            // 所以当 i >= 2 时，dp[i-1] 可以加入 max 的候选
            if (i >= 1) {
                max = Math.max(max, dp[i-1]);
            }
        }

        System.out.println(ans);
    }
}

卖货

题目链接

解题思路(动态规划 + 栈优化)

小蓝经营一家零售店，每天的进货记为 1，出货记为 -1。一个合法的经营记录需满足：

总进货数 = 总出货数（即子数组和为 0）；
任何时候库存不能为负（即任意前缀和 ≥ 0）。

给定一个长度为 n 的操作序列（仅含 1 和 -1），求其中有多少个连续子数组是合法的。

初步思路：暴力枚举（前缀和）

最直观的做法是枚举所有子数组：

枚举起始位置 i；
从 i 向右扩展，维护当前前缀和 cur；
若 cur < 0，说明已出现“无货销售”，后续不可能合法，直接 break；
若 cur == 0，说明 [i, j] 是一个合法子数组，答案加一。

⚠️ 缺点

时间复杂度为 O(n^2) ；
当 n \approx 2 \times 10^{5} 时，必然超时。

优化思路：转化为括号匹配问题

观察发现：

1 相当于左括号 '('；
-1 相当于右括号 ')'；
合法子数组 ⇨ 合法括号子串。

对于一个合法括号串，它要么是：

基础型：() → 对应 [1, -1]
嵌套型：(A) → 外层包裹一个合法串
拼接型：AB → 两个合法串并列

于是问题转化为：统计字符串中所有合法括号子串的个数。

注意：不是最长长度，而是总数。例如 "()()" 包含 3 个合法子串：[0,1]、[2,3]、[0,3]。

高效解法：动态规划 + 栈（O(n)）

核心思想

我们用栈来模拟括号匹配，同时用 DP 数组 记录以每个位置结尾的合法子串数量。

状态定义

设 dp[i] 表示：以位置 i 结尾的合法括号子串的个数。

实际上，由于合法括号结构的特性，dp[i] 表示的是：在 i 处完成匹配后，能形成的新合法块数（包括拼接前面的结果）。

转移逻辑

若 nums[i] == 1（左括号）：压入栈，dp[i] = 0；
若 nums[i] == -1（右括号）且栈非空：
- 弹出栈顶 j（匹配的左括号位置）；
- 则 [j, i] 是一个合法子串；
- 若 j > 0，则前面 dp[j-1] 表示以 j-1 结尾的合法结构，可与当前 [j,i] 拼接；
- 因此：
  dp[i] = dp[j - 1] + 1

最终答案为：

\text{ans} = \sum_{i=0}^{n-1} dp[i]

正确性示例

输入：[1, -1, 1, -1]（即 "()()"）

i	nums[i]	栈操作	dp[i] 计算	dp[i]
0	1	push(0)	—	0
1	-1	pop → j=0	dp[-1]=0 → 0+1=1	1
2	1	push(2)	—	0
3	-1	pop → j=2	dp[1]=1 → 1+1=2	2

总答案 = 1 + 2 = 3，正确！

参考代码

方法一：暴力枚举（前缀和）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        int ans = 0;
        // 枚举每个起点 i
        for (int i = 0; i < n; i++) {
            int cur = 0; // 当前前缀和
            for (int j = i; j < n; j++) {
                cur += nums[j];
                if (cur < 0) break; // 无法继续，后续必非法
                if (cur == 0) ans++;  // [i, j] 是合法子数组
            }
        }
        System.out.println(ans);
    }
}

方法二：动态规划+栈

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // dp[i]: 以位置 i 结尾的合法子串个数（实际是可形成的完整括号块数）
        long[] dp = new long[n]; // 使用 long 防止大数溢出
        int[] stack = new int[n]; // 手动栈，存下标
        int top = -1; // 栈顶指针

        long ans = 0;

        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                // 左括号，入栈
                stack[++top] = i;
            } else {
                // 右括号
                if (top >= 0) {
                    int j = stack[top--]; // 匹配的左括号位置
                    // dp[i] = (j > 0 ? dp[j - 1] : 0) + 1
                    dp[i] = (j == 0 ? 0 : dp[j - 1]) + 1;
                }
                // else: 无法匹配，dp[i] = 0（默认）
            }
            ans += dp[i];
        }

        System.out.println(ans);
    }
}

总结

本题本质是合法括号子串计数；
暴力法适用于小数据，但无法应对 n \sim 2 \times 10^5 ；
通过 栈实现括号匹配 + DP 记录历史合法结构，可在 O(n) 时间内高效求解；
关键转移式：dp[i] = dp[j - 1] + 1，体现了“拼接已有合法段”的思想。

结果为真的序列

题目链接

解题思路(线性递推型DP)

给定一个长度为 n 的字符串 s，仅包含字符 '0'、'1'、'2'，分别表示逻辑运算符 与（&）、或（|）、异或（^）。
我们需要构造一个长度为 n+1 的布尔序列 S = (S_0, S_1, \dots, S_n) ，其中每个 S_i \in \{0,1\} ，并按顺序从左到右依次执行运算：

(((S_0 \ op_0\ S_1) \ op_1\ S_2) \ op_2\ \cdots ) \ op_{n-1}\ S_n

要求最终结果为 1（true）。问：有多少种不同的 S 构造方案？答案对 998244353 取模。

核心观察

运算无优先级，严格从左到右；
每一步的结果只依赖于前一步的值和当前变量；
因此适合使用 动态规划（DP），状态只需记录“当前结果是 0 还是 1”。

状态定义

设 dp[i][v] 表示：使用前 i+1 个变量 S_0 到 S_i ，以及前 i 个运算符 a[0] 到 a[i-1] ，使得当前表达式结果为 v（v = 0 或 1）的方案数。

初始状态：
- dp[0][0] = 1（ S_0 = 0 ）
- dp[0][1] = 1（ S_0 = 1 ）

状态转移

对于第 i 步（ 1 \le i \le n ）：

已知前一步结果为 prev（0 或 1），有 dp[i-1][prev] 种方案；
当前变量 S_i 可取 0 或 1；
根据运算符 op=a[i-1]，计算新结果 cur = prev op S_i；
将方案数累加到 dp[i][cur]。

由于只有 2×2=4 种组合，我们可以显式展开所有情况，使逻辑清晰易懂。

参考代码

版本一：高可读性（推荐理解）

import java.util.Scanner;

public class Main {
    private static final int MOD = 998244353;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String a = sc.next();

        // dp[i][0/1] 表示前 i + 1 个数字使用前i个操作符，结果为 0/1 的方案数
        long[][] dp = new long[n + 1][2];
        dp[0][0] = 1; // 如果只有一个变量，且结果为false，只有一种方案
        dp[0][1] = 1; // 如果只有一个变量，且结果为true，只有一种方案

        for (int i = 1; i <= n; i++) {
            char op = a.charAt(i - 1); // 当前运算符

            long prev0 = dp[i - 1][0]; // 前 i 个变量结果为 0 的方案数
            long prev1 = dp[i - 1][1]; // 前 i 个变量结果为 1 的方案数

            if (op == '0') { // &
                // 当前 S[i] 可选 0 或 1
                dp[i][0] += prev0; // 0 & 0 = 0
                dp[i][0] += prev0; // 0 & 1 = 0
                dp[i][0] += prev1; // 1 & 0 = 0
                dp[i][1] += prev1; // 1 & 1 = 1

            } else if (op == '1') { // |
                dp[i][0] += prev0; // 0 | 0 = 0
                dp[i][1] += prev0; // 0 | 1 = 1
                dp[i][1] += prev1; // 1 | 0 = 1
                dp[i][1] += prev1; // 1 | 1 = 1

            } else if (op == '2') { // ^
                dp[i][0] += prev0; // 0 ^ 0 = 0
                dp[i][1] += prev0; // 0 ^ 1 = 1
                dp[i][1] += prev1; // 1 ^ 0 = 1
                dp[i][0] += prev1; // 1 ^ 1 = 0
            }

            // 每一步取模
            dp[i][0] %= MOD;
            dp[i][1] %= MOD;
        }

        System.out.println(dp[n][1]);
    }
}

版本二：紧凑写法（适合熟练后使用）

import java.util.Scanner;

public class Main {
    private static final int MOD = 998244353;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String a = sc.next();

        // dp[i][0/1] 表示前 i + 1 个数字使用前i个操作符，结果为 0/1 的方案数
        long[][] dp = new long[n + 1][2];
        dp[0][0] = 1; // 如果只有一个变量，且结果为false，只有一种方案
        dp[0][1] = 1; // 如果只有一个变量，且结果为true，只有一种方案

        for (int i = 1; i <= n; i++) {
            int op = a.charAt(i - 1) - '0';
            for (int prev = 0; prev < 2; prev++) { // 前一个操作结果
                for (int s_i = 0; s_i < 2; s_i++) { // 遍历每个变量(0,1,2)
                    int result = compute(prev, s_i, op);
                    dp[i][result] = (dp[i][result] + dp[i - 1][prev]) % MOD;
                }
            }
        }

        System.out.println(dp[n][1]);
    }

    private static int compute(int a, int b, int op) {
        if (op == 0) return a & b;
        if (op == 1) return a | b;
        if (op == 2) return a ^ b;
        return 0;
    }
}

复杂度分析

时间复杂度： O(n) ，每步仅处理常数次操作；
空间复杂度： O(n) ，可进一步优化为 O(1) （只保留前一行），但为清晰起见保留完整 DP 表。

题目

迪沃斯定理

解题思路（最少划分上升子序列问题 · 四个动态规划解法）

问题拆解

核心观察：冲突与划分下界

动态规划设计

参考代码

接龙数列

解题思路(动态规划求最长接龙子序列)

问题转化

方法一：朴素DP，适用于小数据

方法二：状态压缩 DP（O(n)，AC 解法）

辅助函数：提取首位与末位

参考代码

方法一：O(n²)超时无法AC

方法二：AC代码，换一种 dp定义（maxLen就是 dp数组）

松散子序列

解题思路(动态规划)

问题理解

动态规划设计

状态定义

状态转移

优化技巧

最终答案

辅助映射

参考代码

卖货

解题思路(动态规划 + 栈优化)

初步思路：暴力枚举（前缀和）

优化思路：转化为括号匹配问题

高效解法：动态规划 + 栈（O(n)）

正确性示例

参考代码

方法一：暴力枚举（前缀和）

方法二：动态规划+栈

总结

结果为真的序列

解题思路(线性递推型DP)

核心观察

状态定义

状态转移

参考代码

版本一：高可读性（推荐理解）

版本二：紧凑写法（适合熟练后使用）

复杂度分析

智环社团第二次摸底测试题解

蓝桥杯第9次带练

罗文彬

方法二：AC代码，换一种 `dp`定义（`maxLen`就是 `dp`数组）