✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

京东-2025.11.15

题目一：图书馆藏书整理

1️⃣：将原序列中相邻相同的元素合并，简化问题规模

2️⃣：使用区间 DP 求解最少操作次数

3️⃣：状态转移时寻找相同元素进行优化合并

难度：中等

题目二：迷宫探险路线

1️⃣：通过枚举找到递推规律 f(n) = 2·f(n-1) + f(n-2)

2️⃣：使用矩阵快速幂优化计算过程

3️⃣：在 O(log n) 时间内求解结果并取模

难度：中等

1. 图书馆藏书整理

问题描述

K 小姐是一位图书馆管理员，她负责管理一排书架上的 本书籍。每本书都有一个类别编号，K 小姐希望按照目标编号序列 来重新整理这些书籍的类别标签。初始状态下，所有书籍的类别标签都是空白的。

K 小姐每次可以选择一个连续的书架区间 ，将这个区间内所有书籍的类别标签统一设置为某个编号 。由于工作繁忙，K 小姐希望用最少的操作次数完成整理工作。请你帮她计算一下最少需要多少次操作。

输入格式

第一行包含一个正整数 ，表示书籍的数量。

第二行包含 个正整数，依次表示目标类别编号序列 （ 为第 本书的目标类别编号）。

输出格式

输出一个正整数，表示最少需要的操作次数。

样例输入

8
4 4 1 1 1 4 4 4

样例输出

2

数据范围

样例	解释说明
样例1	初始所有书籍标签为空。第一次操作可以将整个区间 标记为 ，第二次操作将区间 标记为 。这样只需 次操作即可完成目标配置。

题解

这道题本质上是一个区间涂色问题。咱们要做的就是用最少的次数，把一排书的标签涂成目标样子。

先来理解一下问题：每次操作可以选一段连续的区间，把这段区间内的所有标签统一涂成某个值。关键观察是，相邻且相同的目标值可以看作一个整体，这样能大大简化问题。

比如序列 4 4 1 1 1 4 4 4，可以压缩成 4 1 4 这样一个更短的序列，长度从 8 变成了 3。

接下来用区间 DP 来解决。定义 dp[i][j] 表示把压缩后序列的第 到第 个元素涂成目标所需的最少操作次数。

基础情况很简单：dp[i][i] = 1，单个元素只需要涂一次。

状态转移时，考虑最后一个元素 ：

• 最基本的做法是先处理 ，再单独涂 ，需要 dp[i][j-1] + 1 次操作
• 但如果在 范围内存在某个位置 的值等于 ，那就有优化空间了。我们可以在涂 的时候把 一起涂了，这样就能省一次操作。具体来说：dp[i][j] = dp[i][k] + dp[k+1][j-1]

为什么能这样优化呢？因为如果 ，那么最后一次涂 的操作可以延伸到涂 ，前提是中间部分 已经处理好了。

算法步骤：

1. 先遍历原序列，将相邻相同的元素合并，得到长度为 的新序列
2. 初始化 dp[i][i] = 1
3. 按区间长度从小到大枚举，对每个区间 ，尝试所有可能的分割点
4. 最终答案是 dp[1][m]

时间复杂度是 ，其中 ，完全可以接受。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n = int(input())
    b = list(map(int, input().split()))
    
    # 合并相邻相同元素
    a = [b[0]]
    for i in range(1, n):
        if b[i] != b[i-1]:
            a.append(b[i])
    
    m = len(a)
    # dp[i][j] 表示处理 a[i:j+1] 的最小操作数
    dp = [[0] * m for _ in range(m)]
    
    # 初始化：单个元素需要 1 次操作
    for i in range(m):
        dp[i][i] = 1
    
    # 枚举区间长度
    for ln in range(2, m + 1):
        for i in range(m - ln + 1):
            j = i + ln - 1
            # 基础：先处理 [i, j-1]，再单独涂 j
            dp[i][j] = dp[i][j-1] + 1
            # 优化：找到 k 使得 a[k] == a[j]
            for k in range(i, j):
                if a[k] == a[j]:
                    cost = dp[i][k]
                    if k + 1 <= j - 1:
                        cost += dp[k+1][j-1]
                    dp[i][j] = min(dp[i][j], cost)
    
    print(dp[0][m-1])

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int dp[405][405];
int a[405], b[405];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    
    // 合并相邻相同的元素
    int m = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || b[i] != b[i-1]) {
            a[++m] = b[i];
        }
    }
    
    // 初始化单个元素
    for (int i = 1; i <= m; i++) {
        dp[i][i] = 1;
    }
    
    // 按区间长度枚举
    for (int len = 2; len <= m; len++) {
        for (int i = 1; i + len - 1 <= m; i++) {
            int j = i + len - 1;
            // 基础方案：先涂 [i, j-1]，再涂 j
            dp[i][j] = dp[i][j-1] + 1;
            // 寻找优化方案
            for (int k = i; k < j; k++) {
                if (a[k] == a[j]) {
                    int val = dp[i][k];
                    if (k + 1 <= j - 1) {
                        val += dp[k+1][j-1];
                    }
                    dp[i][j] = min(dp[i][j], val);
                }
            }
        }
    }
    
    cout << dp[1][m] << "\n";
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    static int[][] dp = new int[405][405];
    static int[] a = new int[405];
    static int[] b = new int[405];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        String[] tokens = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            b[i] = Integer.parseInt(tokens[i-1]);
        }
        
        // 合并相邻相同元素
        int m = 0;
        for (int i = 1; i <= n; i++) {