企业官网建设流程全解析

最近在整理《挑战程序设计竞赛》初级篇里的POJ习题，动态规划这块我前后刷了三遍，每次重刷都有新的体会。很多人刚接触DP时最大的困惑是：题解看得懂，状态转移方程也能背，但换个题目就不知道怎么下手。初级篇这组DP题恰好能治这个问题，它们不追求难度，但每一道都对应一个高频的DP模型——递推计数、二维阶段DP、带限制的决策DP、区间调度、区间DP。把这些题吃透，后面再看中级篇的树形DP、状压DP，至少不会一上来就被状态设计卡死。

这篇文章适合正在刷《挑战程序设计竞赛》、或者刚刚搞懂递归和搜索、想在动态规划上建立手感的人。我会把每道题的题面抽象、状态定义、转移方程、边界条件和实现细节拆开讲，代码用POJ常见的C++98风格写，尽量让你看完能直接照着写、照着调试。刷题的具体过程踩过的坑也会一并整理出来。

1. 习题总览与DP题型的共同密码

1.1 初级篇DP部分的习题分布

我结合初级篇目录和个人刷题记录，整理了这套DP习题里最有代表性的几道。POJ上的题号比较老，但经典程度完全不受影响。

这几道题大致覆盖了DP初学阶段的全部主干：先有递推和记忆化，然后过渡到二维阶段DP，再延伸到带约束条件的决策DP，最后进入区间DP。很多人刷完一遍觉得“每道题都会，合起来就不会”，根本原因是没有意识到这些题背后的共性。

1.2 动态规划题的共同套路

动态规划说白了就是“递归加记忆化”。你有一个大问题，把它拆成若干个规模更小的子问题，子问题之间存在重叠，那么用一个数组把子问题的答案存下来，就能避免重复计算。这个描述听起来简单，但实际做题时有三件事必须想清楚。

第一是状态设计。你要明确dp[i]或dp[i][j]代表什么含义。这是全题的灵魂。状态定错了，后面的转移方程再漂亮也没用。判断一个状态设计得好不好，有一个很实用的标准：当前状态一旦确定，后续的决策是否只依赖当前状态本身，而不关心之前是怎么走到这个状态的。这个性质叫“无后效性”。如果发现当前决策会受到“怎么走到这里”的影响，那就要在状态里多加一个维度把这个历史信息记录下来。

第二是转移方程。转移的本质是枚举“当前这一步能做的决策”，然后把子问题的答案加起来或者取最值。很多初学者会把转移方程背得很熟，但对“为什么是从这个状态转移过来”没有概念。我建议做一道新题时先写一个暴力DFS，再用数组跳过重复计算的子问题，这样状态设计和转移方程都是顺着递归自然长出来的，比直接凭空猜一个递推式要靠谱得多。

第三是边界初始化。dp数组的底部条件、起点条件、非法状态的初始化，决定了你的答案是否正确。实际刷题时WA的原因里，边界错误基本能排到前两名，后面专门讲。

2. POJ 3176 Cow Bowling：数字三角形里的阶段划分

2.1 题面抽象与自底向上的选择

题目大意是一个数字三角形，从顶部出发，每次可以走到下一层的相邻两个位置，问从顶部到底部经过的数字之和最大是多少。比如三角形有三层，那么每层的每个位置只能从上一层的正上方或者左上方走过来，本质上是一个在三角形网格上求最大路径和的问题。

这个题很多人第一反应是自顶向下递推，也就是从顶部开始，dp[i][j]表示从顶部走到第i行第j列的最大值。这个思路完全可行，但有个小麻烦：顶部只有一个点，而边界位置的“上方”来源只有一个或者没有，初始化的时候要小心上面越界的问题。我更喜欢自底向上，因为底部的每个位置都是天然合法的起点，不需要任何特殊初始化。

自底向上的状态定义是：dp[i][j]表示从三角形底部走到第i行第j列这个位置能获得的最大路径和。转移方程写出来非常对称：

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + tri[i][j]

因为从(i,j)往下走，只能走到下一层的第j列或第j+1列。反过来看，从这两个位置之一走到(i,j)反过来取最大值。整个计算从最后一行往上推，最后答案就是dp[0][0]。这个过程很像从下往上填一张表，一行一行的边界都天然存在，基本上不会写错。

2.2 空间优化：从二维数组到滚动数组

如果直接开二维数组dp[350][350]，对于这道题当然没有任何问题，n最多也就三百多。但滚动数组的思想值得在这里就练起来，因为后面很多题的空间限制没那么宽松。

观察转移方程，第i行只依赖第i+1行，再下面几行算完之后就用不到了。所以可以只用一个一维数组，循环的时候从最后一行往上覆盖。

#include <cstdio> #include <algorithm> using namespace std; int tri[355][355]; int dp[355]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { scanf("%d", &tri[i][j]); } } for (int j = 0; j < n; j++) { dp[j] = tri[n-1][j]; } for (int i = n-2; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[j] = max(dp[j], dp[j+1]) + tri[i][j]; } } printf("%d\n", dp[0]); return 0; }

注意滚动数组更新dp[j]时，dp[j]和dp[j+1]中存放的是下一层的值，也就是还没被当前行覆盖的旧值。因为j是从0往i方向递增的，dp[j+1]还没被本轮更新，依然保留着上一轮的结果，所以可以直接用。这个“后一位还没被覆盖”的特性，和0-1背包里一维数组倒序更新的原理是一样的，区别只是这里恰好要正序遍历。

2.3 这题真正的训练价值

数字三角形之所以被当成DP入门题，不是因为它难，而是因为它把“阶段”这个概念展示得非常直观。每一层就是一个阶段，当前阶段的最优值只由上一个阶段决定。后面遇到网格路径类问题，比如机器人从左上角走到右下角的最小代价，本质上都是同一个套路：找到阶段，定义dp[i][j]表示到达该阶段时的最优值，再写出相邻阶段的状态转移。

我第一次刷这道题时，还把自顶向下的写法也写了一遍，对比之后才理解为什么要考虑边界。建议你也两种都写一次，用一个小三角形手算一下，比看十遍题解都有用。

3. POJ 2229 Sumsets：整数拆分，别急着背包

3.1 题面与递推观察

题目问的是：给定一个正整数n，把它表示成若干个2的幂次方之和，顺序无关，问一共有多少种方案。n的最大范围能到100万，所以肯定不能真去枚举拆分，要找递推关系。

这种题先打表看前几项是最快的。我手工列了一下：

n=1时只有1，答案是1。 n=2时可以是1+1、2，答案是2。 n=3时1+1+1、1+2，答案是2。 n=4时1+1+1+1、1+1+2、2+2、4，答案是4。 n=5是4，n=6时多了一个2+2+1+1和2+1+1+1+1等，答案是6。

规律其实已经出来了：奇数项的答案等于它前面那个偶数的答案，偶数项比前面的项要多出一部分。接下来就是把这个规律变成严格的递推式。

3.2 奇偶分类讨论推导递推式

设dp[n]表示把n拆成2的幂次方之和的方案数，顺序无关。

当n是奇数时，任何拆分方案里都必须有至少一个1。因为拆出来的每一项都是2的幂，如果全是偶数，那它们的和一定是偶数，不可能加出奇数。把这个唯一的“最小单元”1从拆分里去掉，剩下的就是n-1的一个拆分。反过来，给n-1的任意拆分补一个1，就得到一个n的拆分。所以dp[n] = dp[n-1]，对奇数n成立。

当n是偶数时，情况就复杂一点了。按拆分里是否包含1来分类。如果含1，去掉这个1，对应n-1的拆分；如果不含1，那么拆分里的每一项都是偶数的2的幂，也就是至少是2。把每一项都除以2，就得到一个n/2的拆分。反过来，把n/2的每个拆分整体乘以2，就得到一个不含1的偶数n拆分。所以偶数n的答案是这两类方案数之和：

dp[n] = dp[n-1] + dp[n/2]

这个推导的精髓在于：把“是否含1”当作分类标准，拆开来分别对应更小的子问题。组合计数里的很多递推题都靠这种“最小元素分类讨论”来破局，而不是硬套某个背包模型。

3.3 和完全背包的对比与常见误区

很多人看到“用2的幂次方拼凑一个数”，第一反应是把它当成完全背包：物品是1、2、4、8这些2的幂，每种物品无限用，求恰好装满背包的方案数。这个想法本身没有错，用背包也能算，但是复杂度是O(n乘以物品数量)，也就是O(n log n)。题目n到100万时，虽然也能过，但递推方法只需要O(n)，而且代码更短。

真正容易错的是“顺序无关”这四个字。如果题目要求不同的排列顺序也算不同方案，那就不该用这个递推式，而是另一个经典递推：dp[n] = dp[n-1] + dp[n-2]，因为最后一步要么放一个1，要么放一个2（如果是2的幂次方且只考虑1和2的话）。所以拿到计数题，第一件事永远是确认清楚“什么算一种方案”，顺序算不算，这直接决定状态转移长什么样。

实现代码非常短，注意答案要对1e9取模，并且n最大100万，递推数组开全局即可。

#include <cstdio> const int MAXN = 1000000; const int MOD = 1000000000; int dp[MAXN + 5]; int main() { int n; scanf("%d", &n); dp[0] = 1; for (int i = 1; i <= n; i++) { if (i & 1) { dp[i] = dp[i-1]; } else { dp[i] = (dp[i-1] + dp[i/2]) % MOD; } } printf("%d\n", dp[n]); return 0; }

4. POJ 2385 Apple Catching：加一个维度记录限制条件

4.1 题面抽象与状态选择

两棵苹果树，每过一分钟，会有一棵树上掉苹果下来。有一头牛一开始站在第一棵树下，它一共最多可以移动W次，问在T分钟内最多能接到多少苹果。W和T都不超过1000。

这个题如果不加“最多移动W次”的限制，那就太简单了：每分钟在哪棵树下就接哪个，贪心即可。但有了移动次数限制后，你必须知道“接苹果的当前时间点”和“已经移动了多少次”，这两个信息都会影响未来的决策。因此dp状态必须把这两个关键信息都装进去。

定义dp[i][j]表示前i分钟，恰好换了j次树，能接到的最大苹果数。当前位置不需要单独用一维来记录，因为换树次数j的奇偶就能确定当前在哪棵树下：换0次在第一棵，换1次在第二棵，换2次又回到第一棵。这是这个状态设计里最巧妙的一个点，也是节省状态维度的典型手法。

4.2 转移方程的细节

每分钟的事件很简单：要么不换树，继续站在当前树；要么换一次树，站到另一棵树下。然后这一分钟如果当前所在的树刚好掉苹果，就接住，收获加1，否则不加。

转移方程写出来是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + (当前树掉苹果 ? 1 : 0)

其中“当前树掉苹果”的判断方式是：如果j是偶数，当前在第一棵树，那就要看第i分钟的苹果是不是掉在第一棵树下；如果j是奇数，在第二棵树，看掉果位置是否是第二棵。

初始化要非常小心。第1分钟的时候，j只能取0或1。j=0表示没动过，站在第一棵树；j=1表示移动了一次，站在第二棵树。dp[1][0]和dp[1][1]要根据第1分钟苹果掉在哪棵树来置1或0。很多初学者直接把整个dp数组初始化为0，然后从i=1开始循环，但这样第1分钟两个状态的初值会错误输出。

循环时j的范围也不能直接写0到W。前i分钟最多只能换i次树，所以j要控制在0到min(i, W)之间，避免无意义地转移不存在的情况。

4.3 二维滚动数组的写法与倒序原因

这个题的T和W上限都不大，二维数组完全放得下。但我想借着这道题讲一下滚动数组的写法，因为dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-1]，可以把第一维滚掉，只留一个dp[W+1]的一维数组。

如果只用一维数组，每次外层循环对应一分钟，内层循环j就必须从大到小遍历。原因是dp[j]在更新时要用到上一轮的dp[j]和dp[j-1]。如果j从小到大更新，dp[j-1]会被本轮已经算好的新值覆盖，那么算dp[j]时用到的dp[j-1]就不是上一轮的旧值了，导致答案错误。从大到小更新则可以保证dp[j-1]还是上一轮的未覆盖数据。

#include <cstdio> #include <algorithm> using namespace std; int dp[35]; int main() { int T, W; scanf("%d%d", &T, &W); for (int i = 1; i <= T; i++) { int tree; scanf("%d", &tree); for (int j = min(i, W); j >= 0; j--) { int add = 0; if (j % 2 == 0) { add = (tree == 1) ? 1 : 0; } else { add = (tree == 2) ? 1 : 0; } if (j == 0) { dp[j] = dp[j] + add; } else { dp[j] = max(dp[j], dp[j-1]) + add; } } } int ans = 0; for (int j = 0; j <= W; j++) { ans = max(ans, dp[j]); } printf("%d\n", ans); return 0; }

注意这里枚举j到min(i,W)，因为前i分钟不可能换超过i次树。这个细节在POJ上容易被忽略，但一旦改成min(i,W)就能避免很多无谓的数组越界风险。

5. POJ 3616 Milking Time：先排序，再DP的区间调度

5.1 题面抽象成带权区间调度

奶牛在一天内可以被挤奶多次，每次挤奶有一个开始时间s、结束时间e和产奶量v。挤完一次奶后，奶牛需要休息R分钟，才能开始下一次。也就是说，如果选择了一个区间[s,e]，那么下一个区间必须满足下一个开始时间 >= e + R。目标是让总产奶量最大。

很多人的第一反应是贪心：按结束时间排序，然后能接就接，求最大收益。但区间有权值的时候，贪心并不总是正确。局部最优的接法可能会放弃一个产量很大的区间，换来两个产量都很小的区间。这种时候就需要DP，把“选还是不选某个区间”这件事交给递推解决。

先按结束时间e从小到大排序，或者按开始时间s从小到大排序都可以，但排序是必须做的前置工作。只有排好序之后，才能保证dp[j]所代表的“以第j个区间结尾的最优方案”不会把某个在时间线上靠后的区间混进来。

5.2 状态定义与O(M^2)转移

设dp[i]表示“以第i个区间作为当天最后一次挤奶”时的最大总产奶量。那么dp[i]的初值就是v[i]，表示只选择这单独一个区间。接下来枚举所有j < i，只要区间j结束时间加上R不超过区间i的开始时间，就从dp[j] + v[i]转移过来：

dp[i] = max(dp[i], dp[j] + v[i])

最后答案不是dp[M]中的某一个，而是所有dp[i]里的最大值，因为最优方案不一定正好在最后一个区间结束。

这个O(M^2)的转移和最长递增子序列LIS的思路一脉相承。LIS是在找数字上的递增关系，这里是在找时间上的不冲突关系。把“比较大小”换成“开始时间是否晚于结束时间加休息时间”，代码结构就能直接套用。

5.3 用结构体和排序简化实现

实现时定义一个结构体存三个值，排序后做两层循环。

#include <cstdio> #include <algorithm> using namespace std; struct Interval { int s, e, v; }; bool cmp(const Interval &a, const Interval &b) { if (a.s != b.s) return a.s < b.s; return a.e < b.e; } Interval seg[1005]; int dp[1005]; int main() { int N, M, R; scanf("%d%d%d", &N, &M, &R); for (int i = 0; i < M; i++) { scanf("%d%d%d", &seg[i].s, &seg[i].e, &seg[i].v); } sort(seg, seg + M, cmp); int ans = 0; for (int i = 0; i < M; i++) { dp[i] = seg[i].v; for (int j = 0; j < i; j++) { if (seg[j].e + R <= seg[i].s) { dp[i] = max(dp[i], dp[j] + seg[i].v); } } ans = max(ans, dp[i]); } printf("%d\n", ans); return 0; }

这里的休息时间R加在“上一个区间的结束时间”上，再和下一个区间的开始时间比较，逻辑非常清晰。如果你把R加到下一个区间的开始时间上，也就是把seg[i].s替换成seg[i].s - R，效果一样，但可读性会差一些。

5.4 为什么排序是这个题的切入点

做这道题最容易卡住的地方不是DP本身，而是“不知道要先排序”。直接看到区间就套背包思路，会很难受。实际上很多区间调度类的DP题，都依赖“先把所有区间按某个关键时间点排好序，然后问题就变成了一维顺序上的选择问题”。排序的作用是给问题引入一个“方向”，让每个区间只会和它之前的区间发生转移关系，这样就避免了“两个区间互相纠缠”的无后效性破坏。

我刷题时习惯在草稿纸上先画一条时间轴，把样例区间标上去，然后手推一遍dp数组的填充过程。画完就知道背包和区间调度之间到底哪里不一样了。

6. POJ 3280 Cheapest Palindrome：区间DP的左右消去模型

6.1 题面与增加删除的等价性

给定一个字符串，长度不超过2000，再给出每个字符可以增加和删除的代价。问把这个字符串变成回文串的最小总代价。增加一个字符和删除一个字符是两种操作，但本质上它们都能达到同一个目的：让当前不对称的两个端点变得对称。

举例来说，如果当前区间是"abc"，左边是a，右边是c，它们不相等。要让两端变相等，可以选择删掉左边的a，或者删掉右边的c，或者在左边补一个c，或者在右边补一个a。删除和添加在“消去不对称”这个效果上是等价的，区别只是代价不同。所以对每个字符，我们可以只记录一个代价：min(增加代价, 删除代价)。这样状态转移就从四种操作简化成两种“消去端点”的操作。

6.2 区间DP的状态设计与转移

设dp[i][j]表示将原始字符串从第i个字符到第j个字符这一段变成回文串的最小代价。

当s[i] == s[j]时，两端已经相等，内部自然形成回文即可，转移非常简单：

dp[i][j] = dp[i+1][j-1]

当s[i] != s[j]时，需要处理掉其中一个端点。处理掉左边端点就是在左边这个字符上做一次增加或删除，让区间变成(i+1, j)，代价是cost[i]加dp[i+1][j]；处理掉右边端点同理，变成(i, j-1)，代价是cost[j]加dp[i][j-1]。取两者最小值：

dp[i][j] = min(dp[i+1][j] + cost[i], dp[i][j-1] + cost[j])

这里的边界条件是i >= j时dp[i][j] = 0，因为单个字符或空串天然就是回文。

计算顺序上，由于dp[i][j]依赖dp[i+1][j]和dp[i][j-1]，一个是i增大方向，一个是j减小方向，所以不能简单地按i或j单向循环。常用的写法是枚举区间长度len从2到L，然后固定左端点i，右端点j = i + len - 1，这样小区的结果一定在计算大区间之前就已经完成。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s[2005]; int add[256], del[256]; int cost[256]; int dp[2005][2005]; int main() { int n, m; scanf("%d%d", &n, &m); scanf("%s", s); for (int i = 0; i < n; i++) { char ch[2]; int a, d; scanf("%s%d%d", ch, &a, &d); add[ch[0]] = a; del[ch[0]] = d; cost[ch[0]] = min(a, d); } int len = m; for (int L = 2; L <= len; L++) { for (int i = 0; i + L - 1 < len; i++) { int j = i + L - 1; if (s[i] == s[j]) { dp[i][j] = dp[i+1][j-1]; } else { dp[i][j] = min(dp[i+1][j] + cost[s[i]], dp[i][j-1] + cost[s[j]]); } } } printf("%d\n", dp[0][len-1]); return 0; }

6.3 区间DP的通用框架

这道题是典型的区间DP：dp数组的第二维表示区间的右端点，转移时不断缩小区间范围。理解了“两端消去”的模型之后，很多区间DP题都能套同一个框架，比如石子合并、括号匹配。它们的共同点是：大区间的答案依赖某个小区间的答案，所以必须按照区间长度从小到大枚举。

我自己在初学区间DP时，最常犯的错是忘记初始化dp[i][i]和dp[i][i+1]。字符串长度为1时dp[i][i]=0，长度2时要么相等不用花钱，要么不等直接处理一次端点。只要初始化对了，后面的转移就顺了。这个题的数据范围是2000，开2005×2005的int数组没有问题，但如果字符集更大或者字符串更长，就要考虑滚动区间长度来做空间优化。

7. POJ 1065 Wooden Sticks：贪心与DP的进阶衔接

7.1 最少递增链覆盖问题

有若干根木棒，每根有长度和重量。加工设备一次可以处理一序列木棒，要求序列中后一根的长度和重量都不小于前一根，这样算同一组。问最少需要分几组才能把所有木棒加工完。

这个问题第一眼像是贪心排序，实际也确实和贪心有关系。先把木棒按长度升序排序，长度相同的按重量升序排序。排完序后，问题就变成：在重量序列上，每组的加工序列就是一个不下降子序列。问这个重量序列最少能分成多少个不下降子序列。根据一个经典结论，这个最小划分数恰好等于原序列的最长严格下降子序列的长度。

这个结论等于在说：如果重量序列有一个长度为k的严格下降子序列，那这k根木棒两两之间都不能放在同一个组里，所以至少要k组。而反过来又总能构造出k组把序列完全覆盖。这个定理叫Dilworth定理，在算法竞赛里经常以“最少导弹拦截系统”之类的题目出现。

7.2 用LIS的思想写最长下降子序列

求最长下降子序列可以用经典的O(n^2)DP，也可以用贪心加二分把复杂度降到O(n log n)。这里我们只需要O(n^2)就足够了，因为n很小。

dp[i]表示以第i个元素结尾的最长严格下降子序列长度。转移就是枚举前方的j，如果w[j] > w[i]，则dp[i] = max(dp[i], dp[j] + 1)。最后答案取所有dp的最大值。注意这里要求的是“严格下降”，等于的情况并不算，因为长度和重量都相等时可以放在同一组里。

7.3 为什么把这题放在初级篇之后

严格来说，Wooden Sticks并不算纯DP题，它更偏向“贪心排序+LIS模型”的综合题。排在初级篇末尾的价值在于让你意识到：很多DP题并不是贴着一个“动态规划”标签出现在你面前的，它可能披着贪心、排序、搜索的外衣。能不能从题面里识别出底层的DP模型，是竞赛解题最核心的能力。

我刷这道题的时候最大的收获不是记住了Dilworth定理，而是养成了一种习惯：遇到“最少分成多少组才能满足某个相邻条件”的问题，先想排序，再想序列上的子序列结构，而不是盲目贪心。这个习惯在后面很多题里都救过我。

8. 刷题避坑与调试经验

8.1 多组输入和输出格式的经典坑

POJ老题里多组数据特别常见，Wooden Sticks就是一个多组输入，第一行是测试数据组数T，每组里又有自己的n和对应的木棒数据。很多人在本地测试单组数据能过，交上去WA，就是因为没有用while(T--)包住，或者scanf没有判断EOF。多组输入时还要注意每组之间数组清空，尤其是dp数组、计数器之类的全局变量，不清空会带上上一组的结果，答案直接错。

除了多组输入，输出格式也很致命。有的题要求两个输出之间空一行，有的不能空，有的每行结尾不能有多余空格。提交前先把样例的输出格式复制一遍，肉眼比对有没有细微差异。不要小看这个，因为格式错误在POJ上也是WA而不是PE。

8.2 边界初始化是WA的头号来源

DP题的WA原因里，边界初始化错误比转移方程写错更常见。数字三角形的dp初始化要放在最后一行；Apple Catching的第1分钟状态要单独处理；Cheapest Palindrome的dp[i][i]要为0；Sumsets的dp[0]要是1，否则n=1的答案会变成0。这些细节单个拎出来都不难，但混在一起就非常容易漏。

我的建议是每道题写完后，用题目样例手算一遍dp数组的前几个值，尤其是第一行和第一列。手动模拟一遍能发现大多数初始化问题。如果样例过了但WA，就构造几个小数据再手推一遍。构造数据时优先测最小边界，比如n=1、长度为2的字符串、只有一个区间的情况。这些边界数据往往就是判题机隐藏的考察点。

8.3 滚动数组方向先画图再写代码

滚动数组的遍历方向总是让人头疼。我的经验是不要背“倒序还是正序”的结论，直接在草稿纸上画出dp数组相邻两行之间的依赖关系。如果当前行某个格子依赖上一行相同位置的格子和前一个位置的格子，那用一维数组滚动时，只有从后往前更新才能保证用到的旧值不被覆盖。如果依赖的是相同位置的格子和同行的后一个位置，那可能就要从前往后更新。

Apple Catching里我们用的是从大到小更新，因为dp[j]依赖dp[j-1]的旧值。Cheapest Palindrome里由于枚举顺序是区间长度，天然避免了滚动数组的倒序问题。想清楚依赖关系之后，再决定遍历方向，基本不会错。

8.4 把递归记忆化当递推的辅助工具

最后分享一个我用得很顺的调试方法。如果你面对一道新题一点头绪都没有，先不要急着写递推循环，写一个最朴素的递归搜索，用一个二维或者一维数组做记忆化，把所有子问题的答案存下来。这样写出来的代码一定是对的，只是可能慢一点。在这个正确版本的基础上，观察递归函数的参数变化规律，把“参数变化”翻译成“dp数组的下标变化”，递归改成循环，记忆化数组就是dp数组。很多看起来很玄的转移方程，本来就是从递归里自然转化出来的。

这套方法对初学DP的人尤其好用，因为它把“设计状态”这个难题拆成了两个小步骤：先写递归，再改循环。递归阶段你只需要回答“我当前在做什么决策，这个问题依赖哪些子问题”，不需要关心计算顺序。把递归调用的参数列表当作dp的下标列表，再照着参数之间的依赖关系确定循环方向，问题就迎刃而解。

把这几道题彻底做完、想透，再回头看动态规划，你会发现它并不是什么高不可攀的东西。它本质上就是一种“聪明的枚举”：把每个状态当作一个子问题，把每个决策当作一次转移，然后用数组把答案记住。初级篇这组题刷下来，你至少会收获两样东西：一是看到题目能够判断该用哪种DP模型，二是能够独立设计出正确的状态和转移。

我个人实际刷题时的体会是，动态规划能力的提升主要是靠“手感”和“模式库”的双重积累。手感来自反复手算小样例、打表观察规律；模式库来自对经典模型的总结，比如数字三角形、整数拆分、区间调度、区间消去。初级篇恰恰能让你在最小的时间成本内建立起这两个基础。之后的进阶路上，遇到树形DP、状压DP、优化DP时，你依然会反复用到这几道题里练出来的思考方式。