1. 项目概述从一道COCI博弈题看信奥刷题的深度训练最近在带学生刷信奥信息学奥林匹克题目时遇到了COCI 2021/2022赛季第一轮的这道P7928 “Kamenčići”。很多刚接触博弈论或者动态规划的同学看到题目描述里两个人轮流取石子可能会下意识地觉得这又是一道经典的Nim游戏变种。但实际动手实现时才发现里面有不少“坑”和精妙之处远不是套个模板就能解决的。这道题很好地体现了信奥竞赛的特点它考察的不仅仅是你对C语法的熟悉程度更是将具体问题抽象成数学模型并设计出高效算法的能力。今天我就结合这道题和大家深入聊聊如何用C实现这类带有状态压缩和博弈思想的动态规划问题这不仅是应对比赛的关键对理解算法核心思想也大有裨益。题目大意是有一条排成一行的石子序列每个石子要么是红色的‘C’要么是蓝色的‘N’。Alice和Bob轮流从序列的两端最左或最右取走一个石子。游戏有一个限制任何玩家在任意时刻如果已经取走的红色石子数量达到了某个阈值K则立即判负。Alice先手。两人都采取最优策略问在给定的初始序列下Alice是否有必胜策略。题目给的数据范围是序列长度N最大为350K最大为N。这个规模直接暴力搜索所有游戏状态2^N量级是不可能的必须找到更优的方法。2. 核心思路解析为什么这不是简单的区间DP刚拿到这道题最容易想到的思路可能是区间动态规划Interval DP。我们定义dp[l][r]表示当石子序列剩余区间[l, r]时当前操作玩家的胜负状态。这很符合“两端取石子”这个经典模型。但是这道题的关键约束——红色石子数量上限K——让问题变得复杂了。胜负不仅取决于剩余的区间还取决于游戏历史上双方已经取走了多少个红色石子。换句话说当前操作玩家的决策会受到过去操作历史的影响而不仅仅是当前棋盘状态。2.1 状态定义的陷阱与升级如果我们只定义dp[l][r]我们就丢失了“已取红色石子数”这个关键信息。没有这个信息我们无法判断当前玩家取走一个红色石子后是否会立刻触发失败条件。因此状态必须升级。一个最直接的想法是定义dp[l][r][a][b]其中a是Alice已取的红石数b是Bob已取的红石数。这样状态总数是 O(N^2 * K^2)。当N350K350时这个数量级是 350^2 * 350^2 ≈ 150亿无论在时间还是空间上都是完全不可接受的。我们必须寻找更紧凑的状态表示。这里就需要用到博弈论和动态规划中一个常见的技巧只关心与当前决策直接相关的信息。在这道题中决定游戏是否会立即结束的是“当前操作玩家在取走这个石子后他累计的红石数是否会达到K”。至于对手累计了多少红石对于判断当前操作是否合法即不导致自己立刻输掉没有直接影响。对手的红石数只影响对手后续的决策。但是我们真的需要区分Alice和Bob的红石数吗仔细分析游戏规则两人轮流操作规则是对称的都是取石子失败条件都是自己累计红石数达到K。那么我们可以定义一个状态dp[l][r][c]其中c表示当前操作玩家在操作前已经拥有的红色石子数量。而对手的红石数可以通过总红石数和已进行的轮次间接推算吗有点困难因为双方取走的红石数不一定交替增长。这里需要更巧妙的思路。我们观察到游戏是否结束只取决于是否有玩家的红石数达到K。我们可以把“某玩家红石数达到K”视为一个“终止状态”。那么我们可以从后往前从游戏结束的状态开始倒推胜负关系。定义win(l, r, kA, kB)表示在区间[l, r]剩余且Alice已有kA个红石、Bob已有kB个红石的情况下当前操作玩家注意不一定是Alice是否必胜。如果kA K说明Alice已经输了那么当前操作玩家如果是Bob不战而胜如果kB K同理。但这样还是四维状态。我们需要利用一个关键性质在最优策略下玩家只会关心如何避免自己立刻输掉并迫使对手进入必败状态。因此我们可以将状态设计为dp[l][r][diff]其中diff kA - kB这个差值信息量不够因为不知道绝对值。实际上官方题解和常见的AC做法采用了一种更聪明的状态压缩既然总红石数totalRed是已知的可以从初始序列算出且游戏结束时必然有一个玩家的红石数达到了K另一个玩家的红石数小于K。那么我们可以用当前操作玩家已取的红石数和对手已取的红石数两者中的一个结合总红石数推导出另一个。但更常见的做法是利用两人已取红石数之和这个信息。设takenRed为游戏从开始到现在两人总共取走的红色石子数量。那么如果当前是Alice操作她已取的红石数kA和Bob已取的红石数kB满足kA kB takenRed。我们还需要知道kA和kB各自是多少才能判断Alice取石子是否合法吗需要因为我们要判断Alice取一个红石后kA1是否等于K。这就引出了最终实用的状态定义dp[l][r][c]其中c表示在当前局面之前先手玩家Alice已经取走的红色石子数量。注意这个定义是相对于固定玩家Alice的。那么如何知道当前操作玩家是谁呢我们可以通过剩余区间的长度len r - l 1和初始长度N来推算已经进行了多少轮操作。设已取走的石子总数为N - len。如果(N - len)是偶数说明已经进行了完整的若干轮Alice先手然后Bob为一轮那么当前操作玩家是Alice如果是奇数则当前操作玩家是Bob。知道了当前操作玩家以及Alice已取红石数c我们就能推算出Bob已取的红石数takenRedByBob totalRedTaken - c。其中totalRedTaken是总共被取走的红石数它等于初始总红石数totalRed减去剩余区间[l, r]内的红石数。这个剩余区间内的红石数可以用前缀和prefRed[r] - prefRed[l-1]快速得到。这样一来状态就被压缩到了三维l,r,c。其中l和r的范围是1到Nc的范围是0到K-1因为当cK时Alice已经输了游戏不会进入这个状态。状态总数是 O(N^2 * K)对于 N, K 350最大约为 350 * 350 * 350 ≈ 4千3百万。这个数量级在时间复杂度上依然有风险O(状态数)的转移可能超时但已经是可优化和可接受的范围并且空间上通过滚动数组或精细实现可以管理。注意这里的状态定义c为“Alice已取红石数”是一种基于固定视角的编码方式。它使得状态转移时需要根据当前操作玩家来更新不同的变量。另一种对称的定义是dp[l][r][red]其中red表示“当前操作玩家”已取的红石数。两种方式都可以但前一种在编码时判断当前玩家是谁的逻辑会更清晰一些。我们选择第一种来讲解。2.2 博弈论基础必胜态与必败态在定义好状态后我们需要理解博弈DP的核心必胜态Winning State和必败态Losing State。必败态N-position无论当前玩家如何操作对手都能必胜的状态。必胜态P-position存在至少一种操作使得操作后留给对手的状态是必败态。我们的目标就是计算初始状态(1, N, 0)完整区间Alice还没取红石是否是必胜态。从边界条件开始倒推如果剩余区间为空 (l r)游戏自然结束。此时需要根据cAlice的红石数和totalRedTaken - cBob的红石数来判断谁达到了K。实际上游戏会在某玩家取完石子导致自己红石数达到K时立即结束不会进入空区间状态。所以我们的边界是当某玩家取石子后红石数达到K的那一刻。更直接的边界在状态转移中处理如果当前玩家根据l, r, c和已进行轮次算出在取某个石子后他自己的红石数达到了K那么这个取法是非法的会导致他立即输掉他绝不会选择这个操作。因此在状态转移时我们要跳过所有会导致当前玩家立即失败的操作。如果对于当前状态所有合法的操作都指向对手的必胜态那么当前状态就是必败态。如果存在至少一个合法操作能指向对手的必败态那么当前状态就是必胜态。3. 算法设计与状态转移方程基于上面的分析我们设计算法。首先预处理前缀和prefRed[i]表示序列前i个位置中红色石子‘C’的数量。这样可以在O(1)时间内得到任意区间[l, r]内的红石数redInInterval prefRed[r] - prefRed[l-1]。总红石数totalRed prefRed[N]。定义记忆化搜索函数bool solve(int l, int r, int c)表示在剩余区间[l, r]且Alice已取c个红石的情况下当前操作玩家是否必胜。返回值true表示必胜false表示必败。我们需要计算当前操作玩家是谁以及他已有的红石数。已取石子总数takenTotal N - (r - l 1)已取红石总数takenRed totalRed - (prefRed[r] - prefRed[l-1])Bob已取红石数b takenRed - c当前操作玩家如果takenTotal是偶数说明轮到Alice操作。她已有的红石数 c。如果takenTotal是奇数说明轮到Bob操作。他已有的红石数 b。状态转移 当前操作玩家有两种选择取左端的石子 (s[l])或者取右端的石子 (s[r])。 对于每一种选择我们需要检查取走的这个石子是否是红色‘C’取走后当前玩家的红石数是否会等于K 如果取走后红石数等于K则该操作非法不能选择。如果操作合法则游戏进入下一个状态区间变为[l1, r]取左或[l, r-1]取右。同时需要更新c的值即Alice的红石数。注意c始终代表Alice的红石数。如果当前玩家是Alice她取走一个红石则新的c c 1取走蓝石c c。如果当前玩家是Bob他取走石子不影响Alice的红石数所以c c。然后我们递归调用solve(l, r, c)。这个调用的结果表示对手在新区间和新c下是否必胜。如果存在一种合法操作使得solve(l, r, c)返回false即对手面临必败态那么当前玩家可以采取这个操作迫使对手进入必败态因此当前状态是必胜态返回true。如果所有合法操作都导致solve(l, r, c)返回true即对手总能进入必胜态那么当前状态是必败态返回false。边界情况当l r区间为空时游戏应该已经结束。但根据我们的规则游戏会在玩家取石子后立即判断不会进入空区间。所以我们可以认为l r是一个不会到达的状态或者也可以根据此时的c和b判断但为了简化在记忆化数组中不处理这个状态确保递归不会走到这一步。3.1 状态压缩与实现细节直接开一个dp[351][351][351]的数组内存大约是 351 * 351 * 351 * 1 byte ≈ 43 MB如果使用bool类型。这在空间限制通常为128MB或256MB的信奥比赛中是可以接受的。但要注意我们还需要一个vis[351][351][351]数组来标记状态是否计算过这又会增加一倍内存。我们可以用char或int8_t来存储dp值并用特殊值如-1表示未计算0表示必败1表示必胜这样就可以省去单独的vis数组。递归深度最大为N350在C中通常不会栈溢出但为了效率也可以使用迭代式的DP。不过记忆化搜索的代码更清晰易懂。关键点如何计算当前玩家取石子后的红石数设当前玩家为player其已有红石数为currentRed。如果player是 Alice:currentRed c如果player是 Bob:currentRed b takenRed - c取走的石子颜色color (s[pos] C) ? 1 : 0。 // pos是l或r 取走后红石数newRed currentRed color。 如果newRed K此操作非法。状态转移伪代码bool solve(l, r, c) { if (dp[l][r][c] ! -1) return dp[l][r][c]; int len r - l 1; int takenTotal N - len; int redInInterval prefRed[r] - prefRed[l-1]; int takenRed totalRed - redInInterval; int b takenRed - c; // Bobs red stones bool currentPlayerIsAlice (takenTotal % 2 0); int currentRed currentPlayerIsAlice ? c : b; bool canWin false; // 当前玩家是否能赢 // 尝试取左边 if (l r) { int colorLeft (s[l] C) ? 1 : 0; if (currentRed colorLeft ! K) { // 合法操作 int new_c c; if (currentPlayerIsAlice) { new_c c colorLeft; } // 否则 new_c c (Bob取) bool opponentWillWin solve(l1, r, new_c); if (!opponentWillWin) { canWin true; } } } // 尝试取右边 if (!canWin l r) { // 如果左边已经找到必胜策略就不用检查右边了 int colorRight (s[r] C) ? 1 : 0; if (currentRed colorRight ! K) { int new_c c; if (currentPlayerIsAlice) { new_c c colorRight; } bool opponentWillWin solve(l, r-1, new_c); if (!opponentWillWin) { canWin true; } } } return dp[l][r][c] canWin; }初始调用solve(1, N, 0)。如果返回true则输出DA(Yes)否则输出NE(No)。4. 代码实现与关键技巧下面给出完整的C实现并附上详细注释。#include iostream #include cstring #include string using namespace std; const int MAXN 355; int N, K; string s; // 石子序列下标从1开始 int prefRed[MAXN]; // 红色石子前缀和 int totalRed; // 总红石数 // dp[l][r][c] -1 未计算0 必败1 必胜 char dp[MAXN][MAXN][MAXN]; // 记忆化搜索 // l, r: 当前剩余区间的左右端点闭区间 // c: Alice已经取走的红色石子数量 // 返回值在当前状态下当前操作玩家是否必胜 bool solve(int l, int r, int c) { if (dp[l][r][c] ! -1) { return dp[l][r][c]; } int len r - l 1; int takenTotal N - len; // 已经取走的总石子数 int redInInterval prefRed[r] - prefRed[l-1]; int takenRed totalRed - redInInterval; // 已经取走的红石数 int b takenRed - c; // Bob已经取走的红石数 // 判断当前操作玩家是谁 bool isAliceTurn (takenTotal % 2 0); int currentRed isAliceTurn ? c : b; bool canWin false; // 选项1取左边的石子 s[l] if (l r) { bool isRed (s[l] C); // 检查取走后是否会立即输掉 if (currentRed (isRed ? 1 : 0) K) { int new_c c; if (isAliceTurn) { new_c c (isRed ? 1 : 0); } // 递归计算对手的局面 bool opponentWin solve(l 1, r, new_c); if (!opponentWin) { canWin true; } } } // 选项2取右边的石子 s[r] (只有在左边不能直接赢的情况下才需要检查) if (!canWin l r) { bool isRed (s[r] C); if (currentRed (isRed ? 1 : 0) K) { int new_c c; if (isAliceTurn) { new_c c (isRed ? 1 : 0); } bool opponentWin solve(l, r - 1, new_c); if (!opponentWin) { canWin true; } } } // 如果两种操作都尝试了都无法让对手进入必败态那么当前玩家必败 return dp[l][r][c] canWin; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin N K; cin s; // 为了方便让字符串下标从1开始 s s; // 计算前缀和 prefRed[0] 0; for (int i 1; i N; i) { prefRed[i] prefRed[i-1] (s[i] C); } totalRed prefRed[N]; // 初始化dp数组为-1 memset(dp, -1, sizeof(dp)); // 计算初始状态 bool aliceWins solve(1, N, 0); cout (aliceWins ? DA : NE) endl; return 0; }4.1 实现中的几个关键点与优化字符串下标从1开始这是处理前缀和时的常见技巧可以避免对l-1的下标进行特判让代码更简洁。dp数组类型使用char而非bool或int。bool在C中通常占用1字节但bool数组的存取可能不如char数组高效取决于编译器。用char并赋值为-1, 0, 1 是竞赛中常见的技巧。memset可以快速初始化为-1。递归终止条件在我们的设计中递归会自然进行直到区间无效 (l r)。我们需要在solve函数开始处理这种情况。当l r时意味着石子已经取完。此时游戏应该早已因为某玩家取到第K个红石而结束。所以理论上不会走到这个状态。但为了代码健壮性我们可以定义当l r时这是一个终局状态当前没有玩家可操作。那么上一个取石子的玩家是赢家吗不一定因为可能是他取完石子后游戏正常结束双方红石数都未达K。但根据题目游戏只以“某玩家取到第K个红石”为结束条件不以取完石子为结束。所以如果递归到了l r说明之前的所有操作都避开了K个红石的条件。此时我们需要根据最后一步是谁走的来判断胜负吗其实在l r时玩家取走最后一个石子如果依然没有触发K红石条件游戏实际上就结束了石子取完。这时题目描述没有明确胜负。但仔细思考两人在避免拿到第K个红石的前提下取石子直到石子取完那么谁取到了最后一个石子这需要根据已进行轮次判断。一个更简单的处理方式是在solve函数中当l r时直接返回false。为什么可以这样理解当没有石子可取时当前操作玩家无法进行任何操作根据定义无法操作者输他输了。但在我们的游戏规则里没有“无法操作者输”这一条。实际上为了避免歧义我们应该确保递归不会走到l r。如何确保在l r时玩家取走这最后一个石子。取走后区间变为(l r)。但在取走这个石子前我们会检查取走后是否会导致红石数达到K。如果不会那么取走最后一个石子是合法操作游戏在取走这个动作后结束石子取完。我们不需要再递归进入空区间。因此我们可以修改代码当l r时玩家只有一种选择取走这个石子。如果他取走后不会达到K那么他就执行了这个操作游戏结束。对于调用者来说他执行了一个操作并且这个操作没有立即输那么接下来对手面对空区间。我们定义空区间为“对手无法操作的状态”即对手的必败态。所以在solve函数中当l r时我们可以直接返回false表示当前玩家面对空区间无法操作是必败态。这样逻辑就自洽了。 修改后的边界处理bool solve(int l, int r, int c) { if (l r) { // 没有石子可取了当前玩家无法操作根据定义无操作者输返回必败 return false; } if (dp[l][r][c] ! -1) return dp[l][r][c]; // ... 其余逻辑不变 }这个处理是简洁且正确的。时间复杂度状态数 O(N^2 * K)每个状态最多进行两次递归调用取左或取右。因此总时间复杂度约为 O(N^2 * K)。对于 N350, K350最坏情况运算量约为 350 * 350 * 350 * 2 ≈ 8.5千万次递归调用/状态转移。在2秒的时间限制内C通过记忆化搜索和适当的优化如-O2通常可以通过。但为了更稳定可以尝试用迭代DP自底向上来减少递归开销。空间优化dp[351][351][351]是 ~43MB。如果担心内存可以注意到cAlice的红石数的范围是[0, K-1]而KN。所以没问题。也可以使用short int或int8_t。5. 迭代动态规划实现与性能对比虽然记忆化搜索直观但迭代DP有时更快且避免了递归深度和栈开销。我们可以用递推的方式填满dp表。难点在于确定递推的顺序。状态(l, r, c)依赖于(l1, r, new_c)和(l, r-1, new_c)即区间长度更短的状态。因此我们可以按区间长度len从小到大的顺序进行递推。定义dp[l][r][c]为剩余区间为[l, r]Alice已取c个红石当前操作玩家是否必胜。 初始化当l r时dp[l][r][c] false无法操作必败。但我们的数组下标l和r从1到N所以我们需要处理l r的情况或者更优雅地只计算l r的状态。递推时对于区间[l, r]我们需要知道当前操作玩家是谁。这可以通过已取石子数takenTotal N - (r-l1)的奇偶性判断。同时需要计算takenRed,b等和记忆化搜索中一样。迭代DP代码框架// 初始化dp数组为false for (int l 1; l N1; l) { for (int c 0; c K; c) { dp[l][l-1][c] false; // 空区间必败 } } // 按区间长度从小到大遍历 for (int len 1; len N; len) { for (int l 1; l len - 1 N; l) { int r l len - 1; for (int c 0; c K; c) { // 计算 takenTotal, takenRed, b, isAliceTurn, currentRed int takenTotal N - len; int redInInterval prefRed[r] - prefRed[l-1]; int takenRed totalRed - redInInterval; int b takenRed - c; bool isAliceTurn (takenTotal % 2 0); int currentRed isAliceTurn ? c : b; bool canWin false; // 尝试取左 if (currentRed (s[l]C) K) { int new_c isAliceTurn ? c (s[l]C) : c; if (!dp[l1][r][new_c]) { // 对手必败 canWin true; } } // 尝试取右 if (!canWin currentRed (s[r]C) K) { int new_c isAliceTurn ? c (s[r]C) : c; if (!dp[l][r-1][new_c]) { canWin true; } } dp[l][r][c] canWin; } } } bool aliceWins dp[1][N][0];这种迭代方法避免了递归调用通常常数更小。但三重循环 (len * l * c) 的复杂度与记忆化搜索相同。在实际测试中两者时间相差不大迭代略快一些。记忆化搜索的优点是只计算需要访问的状态而迭代计算了所有状态。对于本题状态几乎都会被访问到所以迭代计算所有状态也可以。6. 常见问题与调试技巧在实现这道题时同学们容易遇到以下几个问题状态定义不清混淆“当前操作玩家”和“Alice”的红石数。务必明确c在状态中的含义并在转移时正确更新。非法操作判断错误判断条件currentRed color K还是currentRed color K题目是“达到K”即等于K就输。所以是。如果写成当K0时虽然题目可能不会出现会出错。前缀和计算错误前缀和数组prefRed[i]通常表示前i个元素的和包括第i个。所以区间[l, r]的和是prefRed[r] - prefRed[l-1]。务必检查l1时的边界确保prefRed[0] 0。递归爆栈或超时N350时递归深度最大350一般不会爆栈。超时可能是因为没有记忆化或者状态转移计算量太大如重复计算前缀和。确保使用记忆化数组并将prefRed、totalRed等预先算好。初始化问题dp数组必须初始化为一个“未计算”的值如-1否则记忆化搜索会错误地返回未初始化的值。输出格式题目要求输出DA或NE注意大小写。调试技巧小数据测试构造简单的例子手动计算。例如N1, K1石子为C。Alice先手取走这个红石她立刻有1个红石达到K1所以她输。输出应为NE。中等数据测试N3, K2石子为CNC。Alice可以先取左边的C红她有1红然后Bob取右边的C红Bob有1红最后Alice取中间的N蓝Alice仍为1红未达到2。石子取完无人达到2红。但游戏是在取石子过程中判断不是结束后。实际上Bob在取右边C时他的红石数变为1未达到2合法。所以最终Alice未输。但我们需要判断Alice是否有必胜策略。可以手动推演如果Alice一开始取左边的C过程如上最终无人达到2红游戏以取完石子结束题目没有定义这种平局情况谁赢。但根据我们的算法当最后石子取完我们定义的l r状态返回false当前玩家无法操作判负。那么最后一步是Alice取走最后一个石子N然后轮到Bob面对空区间Bob无法操作Bob输所以Alice赢这似乎和直觉不符因为游戏可能应该以“谁先拿到第K个红石”为唯一结束方式。这里揭示了题目描述的一个隐含点游戏进行到石子取完如果双方红石数都未达到K那么怎么判查阅原题COCI P7928可以发现题目保证总红石数严格大于K。这意味着游戏一定会在石子取完之前因为某玩家取到第K个红石而结束。所以我们的算法不需要处理石子取完的情况递归也不会走到l r。这是一个重要的题目条件在我们的状态转移中我们只允许取石子后红石数 K的操作。如果所有合法操作都不存在即无论取哪边都会导致自己达到K那么当前玩家就输了。这保证了游戏一定会在过程中结束。 因此我们不需要处理l r的边界情况。在记忆化搜索中如果l r被调用那一定是代码逻辑有误。我们可以加上一个断言assert(l r)或者在函数开头判断if (l r) return false;作为一种防御性编程但理论上不会进入。打印中间状态对于复杂的状态可以输出l, r, c, dp值来检查是否正确。7. 算法扩展与同类问题思考这道题是博弈论结合动态规划的经典题目其核心在于状态设计。它不同于简单的区间DP因为引入了“历史信息”已取红石数。解决这类问题的通用步骤是识别游戏状态找出完全描述当前局面的最小信息集合。通常包括棋盘状态如区间位置和与规则相关的历史状态如已取某种棋子的数量、当前玩家等。状态压缩如果直接表示历史状态导致维度爆炸需要寻找压缩方法。常见技巧有只记录差值比如只记录两人分数差而不是各自分数。利用总和已知总量记录一个量即可推出另一个。对称性利用游戏的对称性减少状态。模运算如果规则是循环的可以用模数压缩。确定必胜/必败态定义清楚边界条件无法操作的状态、立即输的状态。状态转移根据游戏规则枚举当前玩家的所有合法操作检查操作后是否能让对手进入必败态。类似的题目还有取石子游戏变种除了两端取还有一堆石子每次取一定数量但可能有取石子上限或特殊规则。棋盘上的博弈如COCI中的很多题在网格上移动棋子记录某些属性的累积值。带有“阈值”或“资源限制”的博弈就像本题累积某种资源达到阈值就输。这类问题通常需要将资源量纳入状态。对于信奥选手来说刷这类题目的意义不在于背模板而在于锻炼问题抽象和状态设计的能力。在比赛中看到新题要能自己分析出关键状态变量并设计出可行的DP方程。这需要大量的练习和对经典模型的深刻理解。最后关于这道题的具体实现我个人的体会是清晰的定义胜过聪明的技巧。一开始就把c代表什么、当前玩家是谁、如何计算这些关键点写在注释里能避免很多后续的调试时间。对于350的数据范围O(N^2 * K)的算法是可行的边界实现时要注意常数优化比如用前缀和O(1)查询区间红石数用char数组存储dp值等。如果时间卡得很紧可以尝试使用迭代DP并注意循环顺序以利用CPU缓存。