1. 从“赢球票”这道国赛真题说起一次典型的状态压缩DP实战最近在整理蓝桥杯历届国赛的Java真题翻到了第七届那道“赢球票”的题目。说实话第一次看到这个标题我以为是道模拟或者贪心题但仔细读完题目描述再结合“国赛”这个难度标签心里就大概有数了——这又是一道披着游戏外衣的动态规划DP题而且极大概率是状态压缩DP。对于很多从省赛冲上来的同学状态压缩DP是个坎它不像背包问题那样有固定的模板更考验对问题本质的抽象能力和对二进制操作的熟练度。今天我就以这道“赢球票”为例把状态压缩DP从问题分析、状态设计到代码实现的完整链路拆解清楚。无论你是正在备赛的选手还是想巩固DP思想的开发者相信这篇从实战出发的复盘都能给你带来启发。这道题的核心场景可以抽象为给定一个环形排列的卡片序列每张卡片上有一个数字。游戏规则是你可以从任意一张卡片开始顺时针取走卡片但必须满足一个条件你当前手中所有卡片数字之和要严格大于你即将取走的那张卡片的数字。问在所有可能的起始位置和取卡顺序下最多能取走多少张卡片。题目输入是卡片序列输出就是这个最大张数。环形、顺序相关、求最优解这几个关键词一出来动态规划的思路就呼之欲出了。但难点在于取卡的顺序不是固定的我们需要记录“哪些卡片已经被取走了”这个状态而卡片数量题目规模通常在十几到二十张用传统的多维数组记录每个卡片是否被取走布尔数组会导致状态空间爆炸。这时候状态压缩的思想就派上用场了用一个整数的二进制位来表示每张卡片的取舍状态0表示未取1表示已取。2. 问题拆解为什么状态压缩DP是正解在动手写代码之前我们必须彻底理解为什么其他思路走不通以及状态压缩DP是如何精准匹配此题所有约束的。我们先尝试几种最容易想到的“弯路”。2.1 贪心策略为何失效最直观的想法是贪心每次都从剩余卡片中选择数字小于当前手牌总和且数字最大的那张拿这样手牌总和增长得快似乎能拿更多。这个策略在环形且起始点任意的条件下几乎必然失败。举个反例卡片序列为 [1, 100, 2, 3]。假设从卡片1数字1开始。贪心手牌{1}总和1。可选的下一张是100因为环形顺时针下一张是100或2如果跳着选规则通常是顺时针连续取但题目允许从任意开始取走过程呢这里需要仔细审题。原题描述通常是“从某张开始顺时针取当要取的卡片数字大于手中卡片数字之和时停止”。这意味着取卡过程必须是连续的不能跳着选这是一个关键点我最初也差点误解。如果必须是连续取那么策略就完全不同了。我们假设一个稍复杂的例子环形序列[5, 1, 10, 2]。从5开始手牌和5下一张15可取手牌和变为6下一张106停止。总共取2张。但如果从1开始手牌和1下一张101直接停止只取1张。可见结果与起始点有关。但如果我们允许非连续选取即跳过一些卡片那么问题就更复杂了但题目通常会是连续取因为非连续选取的约束会更复杂。我们回到常规理解也是多数真题的考法游戏是连续的你决定一个起点然后顺时针一张一张尝试拿能拿就拿不能拿当前卡片数字手牌和就立刻停止。那么这就变成了一个简单的模拟题枚举每个起点模拟拿卡过程。但这样对吗如果只是这样题目难度就太低了不符合国赛定位。仔细回想第七届国赛的“赢球票”可能还有另一个关键规则“可以自由选择起始点但一旦选定起点开始取卡取卡的方向顺时针就固定了并且当遇到一张不能取的卡片时游戏不是立即停止而是你可以选择‘跳过’这张牌即不取它继续尝试取它后面的牌吗” 很多同学的记忆模糊点就在这里。实际上根据可靠的真题回顾这道“赢球票”的规则更可能是卡片摆成一圈你选择一个起点然后沿着顺时针方向依次查看每张卡片。对于当前查看的卡片你可以选择‘取走’或‘跳过’。但‘取走’的前提是你手中已有卡片数字之和严格大于这张卡片的数字。你的目标是最大化取走的卡片总数。这个“跳过”机制的存在一下子将问题从简单模拟变成了一个决策问题并且由于可以跳过取卡的顺序就不再是固定的顺时针连续序列了你需要在每个位置做出决策。这正是动态规划的用武之地。而“跳过”操作使得我们需要记录之前做过决策的卡片状态但由于是环形的且起点任意状态设计变得棘手。状态压缩DP通过二进制位掩码来记录哪些卡片被取走了完美解决了“状态记录”的问题。2.2 状态设计与转移方程推导假设有N张卡片编号0到N-1。由于是环形的我们考虑破环成链枚举一个起点i将环形问题转化为以i为起点的线性问题长度为N。但这样需要枚举N次每次做一次DP复杂度是O(N * 2^N * N)在N20时蓝桥杯常见规模是可接受的20 * 2^20 * 20 ≈ 4亿在Java优化下有些临界但通常可行。我们定义dp[mask]表示当卡片被取走的状态为maskmask的二进制第k位为1表示卡片k被取走了时当前手中卡片数字之和的最大值。注意这里dp存的是“和”而不是卡片张数。因为我们的决策能否取下一张卡只依赖于当前手牌之和而与具体取了哪几张无关。我们最终要求的是能取到的最多卡片数量也就是mask中1的位数最多且在该mask状态下dp[mask]是一个有效值非负初始化为-1表示不可达。初始状态当我们选择一张卡片k作为第一张牌时没有前置条件只要这张牌的数字不是负数题目通常数字为正我们就可以取它。因此对于只取了卡片k的状态mask (1 k)dp[mask] card[k]。状态转移我们从当前状态mask表示已取卡集合出发寻找下一张可以取的卡片jj不在mask中。要取卡片j需要满足当前手牌之和dp[mask] card[j]。如果满足那么我们可以转移到新状态newMask mask | (1 j)并且新的手牌之和为dp[mask] card[j]。我们需要用这个值去更新dp[newMask]取最大值因为可能有多种方式达到同样的newMask状态我们保留手牌和最大的那种这样对后续取卡更有利。转移方程dp[newMask] max(dp[newMask], dp[mask] card[j])。最终答案遍历所有可能的状态mask如果dp[mask]是有效值0那么该状态对应的取卡数量就是Integer.bitCount(mask)即mask中1的个数。取所有有效状态中bitCount的最大值即为答案。但是这里有一个巨大的陷阱也是本题最精妙的地方游戏是顺时针进行的吗在我们上面的DP定义中转移时我们可以选择任意一张还未取的卡片j这实际上隐含了“可以跳着取且方向任意”的假设。这与题目中“顺时针”查看的约束可能不符。如果必须严格按照顺时针顺序只是每张卡可以选择取或跳过那么状态设计就需要加入“当前查看到了哪张卡片”这个维度。这会将状态从dp[mask]变成dp[mask][pos]其中pos表示当前查看到了环上的哪个位置0~N-1。复杂度变为O(N * 2^N * N)空间复杂度也增加但在N20时依然可解。为了普适性我们假设题目是最一般的考法环形必须顺时针依次决策每张卡取或跳过起点任意。我们按这个最复杂的约束来推导因为它涵盖了其他简单情况。3. 破环成链与精确状态定义处理环形约束处理环形问题的经典方法是“破环成链”将原数组复制一份接在后面形成一个长度为2N的数组。然后我们枚举起点i (0 i N)考虑从i开始的连续N张卡片即card[i], card[i1], ..., card[iN-1]在这个线性序列上进行DP。最终答案就是所有枚举起点的结果中的最大值。现在我们定义在给定起点i的线性序列上的DP状态。设dp[mask][j]表示在处理到线性序列中第j个位置相对位置从0到N-1时已取卡的状态为mask这个mask是针对这N个位置而言的并且当前手中卡片数字之和的最大值。这里j的含义是“我们已经考虑并决策了前j张卡片0到j-1当前正准备决策第j张卡片”。注意mask中1的位数不一定等于j因为有些卡片被跳过了。初始化dp[0][0] 0表示在起点还未考虑任何卡片手牌和为0。其他状态初始化为-1不可达。状态转移对于每个状态dp[mask][j]如果可达我们此时面临第j张卡片设其数字为val。我们有两种选择跳过那么状态转移到dp[mask][j1]手牌和不变。即dp[mask][j1] max(dp[mask][j1], dp[mask][j])。取走前提是当前手牌和dp[mask][j] val。取走后新状态mask的第j位变为1假设我们为这个线性序列的每个位置分配一个独立的位但注意我们只关心取走了哪些卡片而卡片在环形中的原始编号是(ij)%N。为了在mask中唯一标识一张卡片我们应该用卡片在环形中的原始编号作为位的索引而不是线性序列中的位置j。否则不同起点枚举的mask无法统一。这是一个关键细节。 因此我们需要一个映射线性序列位置j - 环形原始索引idx (i j) % N。取走操作的条件是dp[mask][j] val转移后的新mask是mask mask | (1 idx)新状态是dp[mask][j1]新手牌和为dp[mask][j] val。即dp[mask][j1] max(dp[mask][j1], dp[mask][j] val)。边界与答案当j N时表示我们已经对从起点i开始的连续N张卡片都做出了决策取或跳过。此时状态dp[mask][N]中的mask就记录了从起点i开始按照顺时针顺序最终取走了哪些卡片原始环形中的卡片。对于所有可达的dp[mask][N]值0mask中1的个数就是该策略下取走的卡片数。我们记录其最大值。枚举所有起点i取全局最大值。这个DP状态是dp[1N][N1]对于每个起点i我们需要计算一次DP。总时间复杂度为O(N * (2^N * N))。当N20时2^N ≈ 100万N * 2^N * N ≈ 20 * 100万 * 20 40亿这个计算量在2秒的时限内对Java来说非常紧张很可能超时。因此我们需要优化。4. 算法优化对称性剪枝与DP维度优化面对可能超时的问题我们必须思考优化策略。优化通常从状态定义和转移入手。4.1 利用环形对称性剪枝由于卡片是环形的很多起点本质上是等价的。例如卡片序列是[1,2,3,4,5]从1开始和从3开始如果序列是均匀的可能最优解是相同的。但严格来说我们不能直接认为所有起点等价。不过我们可以观察到一个性质最优解至少会取走一张卡片。假设最优解取走的卡片集合为S那么S中卡片数字之和一定大于S中任意一张卡片的数字因为取每张卡时手牌和都大于该卡数字而手牌和是递增的。那么我们可以断言最优解中取走的第一张卡片一定是整个集合S中数字最小的那张如果不是假设第一张取的是a但S中有更小的b还没取那么取a时手牌和为0刚开始不对取第一张卡时没有“当前手牌和大于卡片数字”的限制题目规则是取第一张卡时没有前置条件吗需要再确认规则。常见设定是游戏开始时手牌和为0第一张卡可以任意取没有限制。那么“第一张卡取S中最小”这个性质就不一定成立了。因此起点剪枝需要小心。一个更安全的优化是由于是环形且我们破环成链后DP对于每个起点i的DP过程其状态dp[mask][j]中的mask记录的是原始卡片索引。我们发现枚举所有起点i会有大量的重复计算。因为环形序列旋转后本质上是同一个环。我们可以固定一个参考点比如总是认为我们第一次取卡的动作发生在某张卡片上。假设我们强制规定取的第一张卡必须是所有卡片中数字最小的那张如果有多个任选一个。因为如果最优解的第一张卡不是最小的我们总可以通过旋转环使得那张卡出现在我们固定的最小卡位置从而得到一个等价的最优解。这样我们只需要枚举以这张“最小卡”作为起点即第一个被考虑的卡片的情况大大减少了计算量。但实现起来需要对环进行旋转对齐稍微麻烦。4.2 降维优化消除j维度观察状态转移方程dp[mask][j]向dp[mask][j1]或dp[mask][j1]转移其中mask包含了新的卡片。这很像一种按“阶段”j进行的DP。我们能否优化掉j这个维度呢可以如果我们按mask中1的个数即已取卡片数来进行DP。定义dp[mask]表示取走mask状态对应的卡片集合后当前手中卡片数字之和的最大值。同时我们需要知道在达到mask状态时我们已经考虑到了环上的哪个位置因为游戏是顺时针进行的我们不能随意取后面的卡片而跳过前面的。换句话说如果mask状态对应取走了一些卡片那么这些卡片在环上的顺序必须是顺时针的。因此仅仅知道mask还不够我们还需要知道最后一张被取走的卡片在环上的位置这样才能知道接下来可以决策哪些卡片。所以更精确的状态是dp[mask][last]表示取走了mask对应的卡片集合且最后一张被取走的卡片是lastlast是环形原始索引时手牌和的最大值。那么下一个可以被考虑取走的卡片必须是从last开始顺时针方向第一个未被取走即不在mask中的卡片吗不完全是因为我们可以“跳过”卡片。所以下一个可以被“取走”的卡片可以是last之后顺时针方向任意一张未被取走的卡片只要满足手牌和大于其数字。但是“跳过”的卡片我们不需要在状态中显式记录因为跳过不影响手牌和也不影响mask。我们只需要在状态转移时对于last之后的每张未被取走的卡片k检查条件dp[mask][last] card[k]如果满足则可以转移到新状态dp[mask|(1k)][k]手牌和更新为dp[mask][last] card[k]。这个状态定义是dp[1N][N]空间复杂度为2^N * N当N20时约为100万 * 20 2000万个整数大约80MB假设int类型在蓝桥杯环境通常内存限制256MB或512MB是可以接受的。时间复杂度为状态数乘以转移开销最坏是O(2^N * N * N)因为每个dp[mask][last]可能需要尝试转移到所有后续的卡片k。这依然是100万 * 20 * 20 40亿次操作非常巨大。我们需要更巧妙的优化。注意到如果dp[mask][last]是有效的那么mask中1的个数就是已取卡片数。我们可以按照mask中1的个数即已取卡片数从小到大进行DP。这样当我们计算dp[mask][last]时所有卡片数比它少的状态都已经计算完毕。这实际上是一种“分层”或“按阶段”的DP。对于每个状态我们尝试取走last之后顺时针的某张卡片k。但如何快速找到last之后有哪些卡片呢我们可以预处理一个“下一个”数组但对于环形和“跳过”机制我们需要遍历last之后的所有卡片直到绕回last之前。这仍然是O(N)的转移。一个关键的突破口是题目要求最大化取卡数量而不是手牌和。因此在dp[mask][last]状态如果有多个不同的last能达到相同的mask和相同的手牌和我们其实只关心是否存在这样的状态。更进一步对于同一个mask我们可能只关心那个能使得手牌和最大的last因为更大的手牌和意味着后续能取走更多卡片的可能性更大。但注意last不同会影响后续可选的卡片集合因为顺时针顺序。所以不能简单地只保留手牌和最大的那个last。看来O(2^N * N * N)的复杂度在N20时确实很极限。我们需要审视题目给定的具体数据范围。蓝桥杯第七届国赛的这道题N很可能小于等于15这样2^153276832768*15*15≈700万就完全在可接受范围内了。很多状态压缩DP的题目N的上限就是15左右20已经是上限且需要很好的优化。因此在实际编码时如果N15我们可以采用dp[mask][last]的状态定义如果N20则需要尝试更优的剪枝或者利用题目特性比如卡片数字范围很小进行优化。5. 代码实现与细节剖析假设我们经过分析确定本题N15我们采用dp[mask][last]的状态定义。下面给出详细的Java实现并逐段解析关键细节和易错点。import java.util.Arrays; import java.util.Scanner; public class WinBallot { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] cards new int[n]; for (int i 0; i n; i) { cards[i] sc.nextInt(); } sc.close(); int totalStates 1 n; // dp[mask][last] 最大手牌和-1表示不可达 int[][] dp new int[totalStates][n]; for (int i 0; i totalStates; i) { Arrays.fill(dp[i], -1); } // 初始化第一张卡可以任意取没有限制根据常见题目规则。 // 但注意如果规则是“当前手牌和卡片数字”才能取那么第一张卡怎么取 // 通常这类游戏的规则是游戏开始时你可以任意选择一张卡片作为起始。 // 我们这里按照“第一张卡无条件取”来实现。 for (int i 0; i n; i) { int mask 1 i; dp[mask][i] cards[i]; // 取走卡片i最后一张是i手牌和为cards[i] } int ans 0; // 按mask中1的个数已取卡片数进行DP for (int mask 1; mask totalStates; mask) { int cnt Integer.bitCount(mask); for (int last 0; last n; last) { if ((mask (1 last)) 0) continue; // last必须在mask中 if (dp[mask][last] 0) continue; // 状态不可达 // 尝试取下一张卡片k for (int k 0; k n; k) { if ((mask (1 k)) ! 0) continue; // k不能在mask中 // 关键k必须是last之后顺时针方向的卡片吗 // 由于是环形且可以跳过理论上我们可以取任意还未取的卡片。 // 但题目约束是“顺时针依次决策”这意味着我们决策卡的顺序是固定的环顺序。 // 我们决策完last卡后下一张要决策的卡是last顺时针方向的下一个位置无论它是否被跳过。 // 所以我们不应该在这里枚举所有k而应该模拟“决策过程”。 // 这说明我们之前的状态设计dp[mask][last]是有缺陷的它没有体现“已经决策到了哪个位置”。 // 我们需要重新思考。 } } } // ... 此处需要重新设计 ... } }上面的代码在关键转移处卡住了因为它暴露了我们状态定义的缺陷。我们需要一个能体现“决策进度”的状态。让我们回到按阶段已决策卡片数DP的思路但结合环形和顺序。重新设计状态设dp[mask]表示当已取卡状态为mask时当前手牌数字之和的最大值。同时我们维护一个辅助信息当前已经沿着顺时针方向从起点开始决策到了环上的哪个位置这个位置不是最后一张取的卡而是我们“指针”所在的位置。假设起点是start我们决策了从start开始的连续若干张卡有些取了有些跳过了当前指针指向下一个待决策的卡片位置pos。那么状态可以用(mask, pos)来表示但pos的范围是0~N-1相对起点。由于起点start是枚举的我们可以将pos理解为从起点开始的偏移量。更可行的方案是外层枚举起点start。对于每个起点我们有一个线性序列card[(start)%N], card[(start1)%N], ..., card[(startN-1)%N]。我们定义dp[mask][j]其中j表示我们已经决策了线性序列中的前j张卡片0 j Nmask记录在这前j张卡片中哪些被取走了注意mask的位对应的是原始环形索引而不是线性序列位置。dp[mask][j]存储当前手牌和。初始化dp[0][0] 0。转移时对于状态(mask, j)我们面临第j张卡片原始索引idx (start j) % N值val cards[idx]。跳过dp[mask][j1] max(dp[mask][j1], dp[mask][j])取走如果dp[mask][j] val则新mask mask | (1idx)dp[mask][j1] max(dp[mask][j1], dp[mask][j] val)最终对于所有dp[mask][N]即决策完一圈mask中1的个数就是取卡数取最大值。这样对于每个起点状态数是O(2^N * N)转移是O(1)。总复杂度O(N * 2^N * N)。当N15时15 * 32768 * 15 ≈ 700万完全可以接受。实现代码如下import java.util.Arrays; import java.util.Scanner; public class WinBallotFinal { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] cards new int[n]; for (int i 0; i n; i) { cards[i] sc.nextInt(); } sc.close(); int totalStates 1 n; int ans 0; // 枚举起点 for (int start 0; start n; start) { // dp[mask][j] 由于j维度只依赖j-1可以用滚动数组优化空间 int[][] dp new int[totalStates][2]; for (int i 0; i totalStates; i) { Arrays.fill(dp[i], -1); } dp[0][0] 0; // 决策0张卡手牌和为0 int cur 0, nxt 1; // 滚动数组指针 for (int j 0; j n; j) { int idx (start j) % n; // 当前决策的卡片原始索引 int val cards[idx]; for (int mask 0; mask totalStates; mask) { if (dp[mask][cur] 0) continue; int currentSum dp[mask][cur]; // 选择1: 跳过 if (dp[mask][nxt] currentSum) { dp[mask][nxt] currentSum; } // 选择2: 取走 (前提是当前手牌和大于卡片数字) // 注意第一张卡可以无条件取吗这里我们初始化dp[0][0]0条件currentSum val对于第一张卡不成立0val? val是正数则不成立。 // 所以需要修改规则对于第一张决策的卡j0可以无条件取。 if (j 0 || currentSum val) { int newMask mask | (1 idx); int newSum currentSum val; if (dp[newMask][nxt] newSum) { dp[newMask][nxt] newSum; } } } // 滚动数组切换 for (int mask 0; mask totalStates; mask) { dp[mask][cur] -1; // 清空当前行为下一轮准备也可以不清理因为会被覆盖 } int tmp cur; cur nxt; nxt tmp; } // 决策完一圈j从0到n-1现在cur指向的是第n轮的结果 for (int mask 0; mask totalStates; mask) { if (dp[mask][cur] 0) { ans Math.max(ans, Integer.bitCount(mask)); } } } System.out.println(ans); } }关键点与易错点解析第一张卡的规则代码中通过if (j 0 || currentSum val)来处理。这是基于“游戏开始时你可以任意取一张卡作为起始”的常见规则。如果题目明确要求“每次取卡都必须满足手牌和大于该卡数字”那么第一张卡就无法被取走游戏无法开始。这显然不合理。所以这个处理是符合逻辑的。滚动数组由于dp[mask][j]只依赖于dp[][j-1]我们可以使用滚动数组将空间复杂度从O(2^N * N)降到O(2^N * 2)这是DP中常见的空间优化技巧。状态初始化dp[0][0] 0是核心起点表示还未做任何决策。答案更新最终对于每个起点start我们遍历所有mask如果dp[mask][cur]有效0就用Integer.bitCount(mask)更新答案。注意我们不需要关心最终的手牌和是多少只关心取卡数量。复杂度三重循环枚举起点O(N)枚举阶段j O(N)枚举状态mask O(2^N)。内层对每个状态的操作是O(1)。总复杂度O(N² * 2^N)。N15时约为225*32768≈735万非常安全。6. 测试与验证构造边界案例写完代码不代表万事大吉必须用各种边界情况测试。对于DP尤其要测试小规模数据并可以尝试暴力搜索DFS对拍确保正确性。测试用例1简单情况输入 3 1 2 3分析无论从哪里开始手牌和0。第一张卡可以取假设规则允许。取1后手牌和1。下一张21不能取但可以跳过。再下一张31不能取。所以最多取1张。如果第一张取3手牌和3下一张13可取手牌和4再下一张24可取手牌和6。所以从3开始顺序为3-1-2可以取3张。但注意环形序列是[1,2,3]。起点是卡片3索引2。决策顺序j0卡片3可取mask包含3和3。j1卡片1因为start2, (21)%3031可取mask包含3和1和4。j2卡片242可取mask包含3,1,2和6。所以答案是3。我们的算法应该输出3。测试用例2所有卡片相同输入 4 5 5 5 5分析第一张取5和5。下一张5条件currentSum val即55为假不能取只能跳过。后续卡片同理。所以无论怎么操作只能取1张。答案应为1。测试用例3递增序列输入 5 1 2 3 4 5分析最优策略是从最大的开始取。起点选5值5。顺序取5和5- 跳过151为真但我们可以选择跳过来尝试取更多吗注意我们目标是最大化取卡数量不是手牌和。如果取1和变成6后面2,3,4都能取总共5张。如果跳过1下一张是252为真取2和7然后3,4,1都能取吗顺序是环形的起点5之后是1,2,3,4。所以策略取5和5- 取151和6- 取262和8- 取383和11- 取4114和15。可以取5张。所以答案是5。测试用例4一个需要“跳过”来获得更优解的例子输入 4 10 1 1 20分析如果从10开始取10和10- 取1101和11- 取1111和12- 2012? 否不能取。共取3张。 如果从20开始取20和20- 1020? 真取10和30- 130? 真取1和31- 131? 真取1和32。共取4张。显然从20开始更优。但我们的算法枚举所有起点会找到这个最优解。我们可以写一个简单的DFS暴力搜索来验证小数据N10下DP结果的正确性确保状态转移和边界条件无误。7. 总结与举一反三状态压缩DP的解题框架通过“赢球票”这道题我们可以提炼出解决状态压缩DP问题的一般思路这对于应对蓝桥杯乃至其他算法竞赛中的类似问题至关重要。7.1 识别状态压缩DP的线索数据规模通常需要记录一个集合的状态如哪些元素被选中、哪些节点被访问且这个集合的大小N在10到20左右2^N在百万级别可接受。问题特征求最优解最大/最小决策过程与历史状态有关且历史状态可以抽象为一个集合。常见场景旅行商问题TSP、棋盘覆盖、子集选取最优排列等。7.2 状态设计核心确定状态集合用什么信息能唯一描述当前决策进展到哪一步通常包括已选择的元素集合用二进制掩码mask表示。附加信息如最后选择的元素last、当前的位置pos、已花费的代价等。附加信息的选择直接影响状态复杂度和转移难度。确定状态值dp[状态]存储什么通常是最优解最大收益、最小代价或是一个布尔值是否可达。初始化找到起点状态通常对应空集或只有一个元素的集合。状态转移从当前状态出发根据题目规则可以做出哪些决策转移到哪些新状态。写出转移方程。最终答案从所有终止状态通常是mask包含所有元素或达到某个条件中找出最优值。7.3 优化技巧滚动数组当状态转移只依赖前一两个阶段时使用滚动数组压缩空间。预处理预处理出每个状态的相关信息如子集、某个位之后的下一个未选元素等加速转移。剪枝利用问题性质提前排除无效状态。例如在“赢球票”中如果当前手牌和已经很大但剩余卡片数字都很小可能不需要再枚举。对称性如环形问题的起点枚举有时可以利用对称性减少计算量。7.4 对于“赢球票”的再思考这道题的一个变种可能是如果规则改为“必须连续取卡不能跳过当遇到不能取的卡时游戏立即结束”。那么问题就简化为枚举起点然后模拟。另一个变种是卡片数字有正有负。那么状态设计中的“手牌和”就可能为负需要仔细考虑转移条件和初始化。在竞赛中拿到题目后最重要的第一步是精确理解规则最好自己构造几个极小的例子模拟一下过程。第二步是分析数据范围这直接决定了算法的可行性。第三步才是设计状态和转移。如果一开始思路错了像我们中间那样发现状态定义有缺陷不要慌回到问题本身重新梳理这是解决问题的正常过程。最后对于Java选手在实现状态压缩DP时要熟练掌握位运算1 i将1左移i位得到第i位为1的数、mask | (1i)将mask第i位置1、mask (1i)判断mask第i位是否为1、mask ^ (1i)将mask第i位取反、Integer.bitCount(mask)计算mask中1的个数等。这些操作是状态压缩DP的基石务必做到熟练、准确。