背包问题是动态规划（DP）中最经典的问题之一，核心是在有限的 “容量” 下，选择物品组合以获得最大 “价值”。下面我会从最基础的01 背包开始，用通俗易懂的方式讲解原理、实现和优化，最后补充常见的变种问题。

C++常用排序算法

数据类型：使用long long防止溢出动态规划的核心是状态定义 + 状态转移方程，先明确dp数组的含义，再推导子问题间的关系。实现时优先保证逻辑正确，再考虑空间优化（如用变量代替数组）。一维 DP 适用于单维度依赖的问题（如斐波那契、LIS），二维 DP 适用于二维网格 / 双维度依赖的问题（如不同路径、最长公共子序列）。

以走迷宫来比喻：深度优先搜索（DFS）：选择一条路（分支）一直走到底，直到死胡同。然后回溯到最近的一个岔路口，换另一条没走过的路继续深入。“不撞南墙不回头”。广度优先搜索（BFS）：站在起点，先探索所有从起点能直接到达的地方（第一层）。然后从这些地方出发，再探索所有它们能直接到达的、且未被探索过的新地方（第二层）。“层层递进，地毯式搜索”。

对于长度为 m 的模式串 P[1…m]：通俗理解：next[j] = 模式串前 j-1 个字符中，最长的相等前后缀的长度 + 1next[j] 表示：当模式串第 j 个字符匹配失败时，应该用模式串的第 next[j] 个字符继续与主串比较计算原理：基于模式串自身的重复结构（前缀后缀匹配）优化：nextval 数组避免重复比较相同字符时间复杂度：计算 next：O(m)匹配：O(n)总复杂度：O(n