1. 从"DP练习-初阶题"这个标题里能读出什么
动态规划这四个字，在算法学习圈子里几乎是"劝退"的代名词。很多人学完基础语法、刷完几十道模拟题之后，第一次接触DP（Dynamic Programming，动态规划）都会有一种"每个字都认识，连起来不知道在说什么"的感觉。而"DP练习-初阶题"这个标题，恰恰指向了最关键的破局点——不是一上来就啃树形DP、状压DP、斜率优化这些高阶内容，而是先把最基础的几种DP模型吃透。
这个标题对应的内容，本质上是一份面向初学者的动态规划入门训练清单。它解决的核心问题是：一个刚学完数组、循环、递归的人，应该按什么顺序、练哪些题，才能建立起对DP的基本感觉。适合的读者非常明确——学过C++或Python基础语法、能写简单的循环和函数、但一看到"状态转移方程"就发懵的编程初学者。如果你已经能独立做出背包问题、最长上升子序列这类题目，那这份内容对你来说偏简单了。
我自己当年入门DP的时候，走过不少弯路。最开始是硬背模板，把01背包的代码背下来，结果遇到"完全背包"就傻眼了，因为不知道两者到底差在哪里。后来才慢慢意识到，DP的核心从来不是代码模板，而是状态定义和转移逻辑这两件事。初阶题的价值就在于，它们的状态定义足够简单、转移逻辑足够直观，能让你把注意力集中在"怎么想"而不是"怎么写"上。
所以这篇内容我会围绕几个最经典的初阶DP模型展开，把每类问题的思考路径、状态设计方法、代码实现细节，以及初学者最容易踩的坑，都掰开揉碎讲清楚。不会堆砌一堆题目编号让你自己去悟，而是把"为什么这样定义状态""为什么转移方程长这样"讲透。这些内容你在任何一本算法教材里都能找到影子，但我会用更贴近实战的方式重新组织，补充那些教材上不会写的经验细节。
2. 入门DP之前必须想清楚的三个认知问题
2.1 DP到底在解决什么类型的问题
很多人对DP的理解停留在"把大问题拆成小问题"这个层面，但这个描述其实不够准确，因为分治也是把大问题拆成小问题。DP真正擅长解决的，是具有重叠子问题和最优子结构的问题。
重叠子问题是什么意思？举个最经典的例子，计算斐波那契数列的第n项。用朴素递归写，f(n) = f(n-1) + f(n-2)，你会发现f(5)被计算了很多次。这就是重叠子问题——同一个子问题被反复求解。DP的做法是把每个子问题的答案存起来，下次需要时直接查表，不再重复计算。
最优子结构则是说，大问题的最优解可以由小问题的最优解推导出来。比如最短路径问题，从A到C经过B的最短路径，一定包含了从A到B的最短路径和从B到C的最短路径。这个性质保证了我们可以从小规模的最优解逐步构建出大规模的最优解。
理解这两点是入门DP的前提。如果你拿到一道题，发现子问题之间互相独立、不会重复出现，那可能用分治或者贪心更合适；如果子问题的最优解无法推导出大问题的最优解，那DP就行不通。初阶题之所以"初阶"，就是因为它们把这两个性质体现得非常明显，几乎不需要你去费力证明。
2.2 记忆化搜索和递推的关系
初学者经常纠结一个问题：DP到底应该用递归加记忆化来写，还是用循环递推来写？我的建议是，入门阶段先用记忆化搜索。
原因很简单。记忆化搜索的代码结构和朴素递归几乎一样，你只需要加一个数组来记录已经算过的状态，就能把指数级的时间复杂度降下来。这种写法非常符合人的直觉——我需要f(n)，那就去看f(n-1)和f(n-2)算过没有，没算过就递归去算，算过了就直接返回。整个思考过程是"自顶向下"的，从大问题出发，需要什么子问题就去求什么子问题。
而递推是"自底向上"的，你得先想清楚最小的子问题是什么，然后按照什么顺序一步步推到目标状态。这个顺序在初阶题里通常很直观（比如从1到n循环），但在复杂问题里，确定正确的递推顺序本身就是一件有难度的事。
我个人的经验是：先用记忆化搜索把问题做出来，确保状态定义和转移逻辑是对的，然后再考虑改写成递推形式。改写的过程本身也能加深你对问题结构的理解。很多初阶题的标准解法都是递推，但你在练习时完全可以用记忆化搜索先跑通，再对照标准解法看差异。
2.3 状态定义的"粒度"怎么把握
这是初学者最容易出问题的地方。状态定义得太粗，信息不够，无法正确转移；定义得太细，状态数量爆炸，时间和空间都扛不住。
举个具体的例子。经典的"爬楼梯"问题：每次可以爬1级或2级，问爬到第n级有多少种方法。状态定义很直接——dp[i]表示爬到第i级的方法数。这个粒度刚刚好，因为第i级的方法数只依赖于第i-1级和第i-2级，不需要知道更多信息。
但如果问题变成"每次可以爬1级或2级，但不能连续爬2级"，那dp[i]就不够用了，因为你还需要知道"到达第i级时最后一步是爬了1级还是2级"。这时候状态就得定义成dp[i][0]和dp[i][1]，分别表示最后一步爬1级和最后一步爬2级的方法数。
所以状态定义的粒度，取决于转移时需要哪些额外信息。一个实用的判断方法是：你先试着用最粗的粒度定义状态，然后看转移方程能不能写出来。如果写不出来，说明缺信息，就加维度；如果写出来了但状态数量太大，就想想有没有冗余信息可以压缩。初阶题的状态维度通常不超过二维，状态数量在10^6以内，这个规模用数组存完全没问题。
3. 线性DP：从一维到二维的思维跃迁
3.1 一维线性DP的典型模式
线性DP是初阶题里出现频率最高的一类，它的特点是状态沿着一个方向线性展开，每个状态只依赖于前面有限个状态。最典型的代表就是前面提到的爬楼梯问题，以及它的各种变体。
以"最大子段和"为例：给一个长度为n的整数数组，求连续子数组的最大和。这道题的状态定义是dp[i]表示以第i个元素结尾的最大子段和。注意这里的关键词是"以第i个元素结尾"，这个限定非常重要，因为它保证了转移的连续性——以第i个元素结尾的子段，要么是第i个元素自己单独成段，要么是接在以第i-1个元素结尾的子段后面。所以转移方程是dp[i] = max(a[i], dp[i-1] + a[i])。
我见过很多初学者在这里犯的错误是，把dp[i]定义成"前i个元素中的最大子段和"。这个定义看起来更自然，但转移就变得很麻烦，因为前i个元素的最大子段和可能根本不包含第i个元素，你没法从dp[i-1]直接推过来。这就是状态定义粒度没把握好——"以第i个元素结尾"这个限定看似多余，实际上是让转移成立的关键。
一维线性DP的另一个典型是"最长上升子序列"（LIS）。朴素做法是dp[i]表示以第i个元素结尾的最长上升子序列长度，转移时枚举所有j < i且a[j] < a[i]的位置，dp[i] = max(dp[j]) + 1。这个做法的时间复杂度是O(n²)，在初阶题的数据范围内完全够用。虽然存在O(n log n)的优化做法，但初阶阶段不建议一上来就学优化，先把O(n²)的朴素DP写熟练，理解状态转移的本质，再去考虑优化。
3.2 二维线性DP的常见场景
当问题涉及两个序列或者两个维度时，就需要二维DP了。最经典的是"最长公共子序列"（LCS）：给两个字符串，求它们的最长公共子序列长度。
状态定义是dp[i][j]表示第一个字符串前i个字符和第二个字符串前j个字符的最长公共子序列长度。转移分两种情况：如果第一个字符串的第i个字符和第二个字符串的第j个字符相同，那它们可以配对，dp[i][j] = dp[i-1][j-1] + 1；如果不同，那它们不可能同时出现在公共子序列的末尾，所以取dp[i-1][j]和dp[i][j-1]的较大值。
这道题的转移逻辑非常清晰，但初学者容易在初始化上出错。dp[0][j]和dp[i][0]都应该初始化为0，因为空字符串和任何字符串的公共子序列长度都是0。这个初始化看起来理所当然，但在更复杂的二维DP里，初始化往往是最容易出问题的地方。
另一个常见的二维DP是"编辑距离"：给两个字符串，求把第一个变成第二个所需的最少操作次数（插入、删除、替换）。状态定义和LCS类似，dp[i][j]表示第一个字符串前i个字符变成第二个字符串前j个字符所需的最少操作数。转移时考虑三种操作对应的代价，取最小值。这道题在初阶题里算是稍有难度的，因为它需要你同时考虑三种转移来源，但本质上还是二维线性DP的框架。
3.3 线性DP的空间优化思路
当你把二维DP写熟练之后，会发现一个问题：很多二维DP的状态转移只依赖于上一行，不依赖于更早的行。这时候就可以用滚动数组把空间从O(n²)降到O(n)。
以LCS为例，dp[i][j]只依赖于dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]。如果我们按行遍历，计算第i行时只需要第i-1行的信息，更早的行已经没用了。所以可以用两个一维数组交替使用，或者用一个一维数组加一个临时变量来保存dp[i-1][j-1]。
不过我要提醒的是，初阶阶段不要急着做空间优化。先把二维数组写对，确保逻辑没问题，再去考虑优化。空间优化虽然能降低内存占用，但会让代码可读性下降，而且容易在细节上出错（比如更新顺序搞反了导致用了本行的新值而不是上一行的旧值）。等你对DP的理解足够深了，空间优化就是水到渠成的事。
4. 背包问题：初阶DP的分水岭
4.1 01背包的状态设计与转移
背包问题是DP入门的一道分水岭。很多人前面学线性DP觉得还行，一到背包就卡住了。其实背包问题的状态定义和线性DP没有本质区别，只是多了一个"容量"维度。
01背包的问题是：有n件物品，每件物品有重量w[i]和价值v[i]，背包容量为W，每件物品只能选或不选，求能装下的最大价值。状态定义是dp[i][j]表示前i件物品在容量为j的背包里能获得的最大价值。转移时考虑第i件物品选不选：不选就是dp[i-1][j]，选就是dp[i-1][j-w[i]] + v[i]（前提是j >= w[i]），取两者较大值。
这个转移方程本身不难理解，但初学者经常在遍历顺序上栽跟头。如果做空间优化用一维数组，容量维度必须从大到小遍历。为什么？因为一维数组dp[j]在更新时会覆盖掉上一行的值，如果从小到大遍历，dp[j-w[i]]可能已经是本行更新过的值了，相当于第i件物品被选了多次，那就变成了完全背包。从大到小遍历才能保证dp[j-w[i]]还是上一行的值，即每件物品只选一次。
这个细节我在初学的时候反复搞混过好几次，每次都是代码跑出来结果不对，对着转移方程看半天看不出问题，最后才发现是遍历顺序反了。所以我的建议是：先用二维数组写，确认逻辑正确后，再改成一维数组，并且刻意记住"01背包容量倒序、完全背包容量正序"这个口诀。
4.2 完全背包与01背包的本质差异
完全背包和01背包的唯一区别是：每件物品可以选无限次。这个差异体现在转移方程上，就是选第i件物品时，状态应该从dp[i][j-w[i]]转移而不是dp[i-1][j-w[i]]。因为选了第i件之后，还可以继续选第i件，所以是在本行的基础上转移。
用二维数组写的话，01背包是dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，完全背包是dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])。注意看，区别就在第二项的i-1变成了i。这个细微的差别，反映的是"每件物品只能用一次"和"每件物品可以用无限次"这两个约束。
用一维数组写的话，01背包容量倒序遍历，完全背包容量正序遍历。正序遍历时，dp[j-w[i]]已经被本行更新过了，正好对应"可以重复选"的语义。所以你看，遍历顺序不是随便定的，它和问题的语义是严格对应的。理解了这一点，就不用死记硬背了。
4.3 多重背包的初阶处理方式
多重背包是每件物品有有限个数量。初阶阶段通常不要求掌握二进制优化或单调队列优化，只需要用最朴素的方式：把每件物品的k个数量拆成k个独立的物品，然后跑01背包。这样做的时间复杂度是O(n * k * W)，在数据范围小的时候完全够用。
虽然这个做法效率不高，但它的好处是不需要额外的思维负担——你只需要把问题转化成已经会做的01背包就行了。初阶阶段最重要的是建立信心和熟练度，而不是追求最优复杂度。等你把01背包和完全背包都写得很熟了，再去学多重背包的优化也不迟。
我个人的经验是，背包问题的学习路径应该是：01背包（二维→一维）→ 完全背包（理解遍历顺序的差异）→ 多重背包（朴素拆分）→ 混合背包（分类讨论）。每一步都确保自己能独立写出代码并且解释清楚为什么这样写，再进入下一步。跳步学习是初学者最容易犯的错误，看起来省时间，实际上后面会花更多时间补回来。
5. 区间DP与树形DP的初阶接触
5.1 区间DP的枚举顺序为什么重要
区间DP的典型问题是"石子合并"：一排石子，每次可以合并相邻的两堆，合并的代价是两堆石子数量之和，求把所有石子合并成一堆的最小总代价。
状态定义是dp[i][j]表示把区间[i, j]内的石子合并成一堆的最小代价。转移时枚举分割点k，把区间分成[i, k]和[k+1, j]两部分，dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i, j))。其中sum(i, j)是区间内石子总数，可以用前缀和快速计算。
这道题的关键在于枚举顺序。你不能按i从1到n、j从1到n的顺序遍历，因为dp[i][j]依赖于比它更短的区间。正确的做法是按区间长度从小到大枚举，先算所有长度为2的区间，再算长度为3的，以此类推。这样保证计算dp[i][j]时，它依赖的所有子区间都已经算好了。
这个"按区间长度枚举"的思路，是区间DP的标志性特征。初学者如果按常规的i、j顺序遍历，会发现用到的子区间还没算出来，结果全错。我在第一次做石子合并的时候就在这里卡了很久，后来才意识到DP的遍历顺序必须满足拓扑序——所有依赖的状态必须先于当前状态被计算。
5.2 树形DP的递归框架
树形DP是在树结构上做DP，通常用递归实现。最经典的初阶题是"没有上司的舞会"：一棵树上的每个节点有一个权值，选出一个节点集合，使得集合中任意两个节点不相邻（即不能同时选父节点和子节点），求最大权值和。
状态定义是dp[u][0]表示不选节点u时以u为根的子树能获得的最大权值，dp[u][1]表示选节点u时的最大权值。转移时遍历u的所有子节点v：如果选了u，那所有子节点都不能选，dp[u][1] += dp[v][0]；如果不选u，那子节点可以选也可以不选，dp[u][0] += max(dp[v][0], dp[v][1])。
树形DP的递归框架很固定：先递归处理所有子节点，再用子节点的结果更新当前节点。这个"后序遍历"的顺序天然满足DP的拓扑序要求，因为子节点的状态一定先于父节点被计算。初阶阶段掌握这个框架就够了，不需要考虑换根DP、树上背包这些进阶内容。
5.3 初阶DP练习的节奏建议
很多人刷题喜欢按题目编号顺序刷，或者随机挑题刷。对于DP这种需要建立思维模式的专题来说，按模型分类刷效率更高。
我的建议是：先集中刷10到15道一维线性DP，把"以某元素结尾"这种状态定义方式刻进肌肉记忆；然后刷10道左右的二维线性DP，熟悉两个维度的转移；接着刷背包问题的三个基本类型，每个类型至少5道；最后接触区间DP和树形DP各3到5道。整个初阶阶段大概50到60道题就够了，关键是每道题都要独立想出来，而不是看题解看出来的。
独立想出来的标准是：你能在不看任何提示的情况下，说出状态定义是什么、转移方程是什么、遍历顺序是什么、初始化怎么做。如果有一项说不清楚，说明这道题你还没真正掌握，需要重新做一遍。这个标准看起来严格，但DP的题型其实很有限，初阶阶段把几十道题真正吃透，后面遇到新题时你会发现大部分都能归入已知的模型。
6. 初阶DP练习中那些没人告诉你的坑
6.1 边界条件处理不当导致的隐蔽错误
DP的边界条件是最容易出错的地方，而且错误往往很隐蔽——样例能过，但提交后某些测试点就是过不了。
以最长上升子序列为例，dp数组应该初始化为1，因为每个元素本身至少构成一个长度为1的上升子序列。如果你初始化为0，当数组只有一个元素时，答案会输出0而不是1。这种错误在样例里可能看不出来，因为样例通常有多个元素，dp值会被后续转移覆盖掉。
再比如背包问题，dp[0][j]和dp[i][0]的初始化。dp[0][j]表示没有物品可选时的最大价值，显然是0；dp[i][0]表示容量为0时的最大价值，也是0。但如果题目要求"恰好装满"，那dp[0][0]应该是0，而dp[0][j]（j > 0）应该是负无穷，表示无法恰好装满。这个区别在初阶题里经常出现，需要根据题意仔细判断。
我的经验是：写完转移方程后，先手动模拟n=1、W=0、数组全负这些边界情况，看看代码输出是否符合预期。这个习惯能帮你提前发现大部分边界问题。
6.2 状态转移方程写对了但答案不对的排查思路
有时候你确信状态定义和转移方程都没问题，但代码跑出来就是不对。这时候可以按以下顺序排查：
第一，检查数组大小。是不是开小了导致越界？是不是开大了导致内存超限？初阶题的数据范围通常在10^3到10^5之间，二维数组要注意n²会不会超过内存限制。
第二，检查遍历顺序。一维DP的遍历方向对不对？二维DP的两层循环嵌套顺序对不对？区间DP是不是按长度枚举的？遍历顺序错了，转移方程再对也没用。
第三，检查初始化。dp数组的初始值是不是符合题意？有没有遗漏某些边界状态的初始化？
第四，检查取模。如果题目要求对结果取模，是不是在每一步转移时都取了模？有没有在中间计算时溢出？
第五，打印中间状态。把dp数组的每一行或每一列打印出来，和手动计算的结果对比，看看从哪一步开始出现偏差。这一步通常能直接定位到问题所在。
6.3 从"能看懂题解"到"能独立写出"的距离
这是初学者最常遇到的困境：看题解觉得理所当然，自己写就写不出来。这个距离的本质是思维模式还没有内化。
看题解时，你是沿着别人的思路走，每一步都有引导，自然觉得顺畅。但独立做题时，你需要自己决定状态怎么定义、转移怎么写，这些决策在题解里往往是一笔带过的，但恰恰是最难的部分。
缩短这个距离的方法只有一个：反复独立推导。一道题看完题解后，关掉题解，从空白文件开始重新写一遍。如果写不出来，再看题解，再关掉，再写。重复这个过程直到你能一气呵成地写出来。这个过程可能很痛苦，但它是唯一有效的路径。
我自己的经验是，一道DP题通常需要独立写3遍以上才能真正掌握。第一遍是理解，第二遍是记忆，第三遍才是内化。那些只写一遍就过的题，过两周再遇到，大概率还是不会。
6.4 关于刷题数量和质量的平衡
初阶DP阶段，我建议质量优先于数量。与其刷100道题但每道都似懂非懂，不如刷30道题但每道都能讲清楚来龙去脉。
判断一道题是否"真正掌握"的标准很简单：你能不能给一个完全不懂DP的人讲明白这道题？如果你能用大白话把状态定义、转移逻辑、遍历顺序都解释清楚，那说明你确实理解了。如果你讲的时候还需要频繁看代码或者用"就是这样的"来搪塞，那说明你只是记住了代码，没有理解思想。
另外，初阶阶段不要追求一题多解。有些题确实有多种DP做法，但初阶阶段掌握一种标准做法就够了。等你把基础模型都吃透了，再回头研究不同解法的优劣，那时候你的判断力才足够做出正确的选择。
7. 把初阶DP练扎实之后的路怎么走
初阶DP练扎实之后，你会发现自己对"状态"和"转移"这两个概念有了直觉。拿到一道新题，你会下意识地去想：这个问题的子问题是什么？子问题之间怎么关联？需要记录哪些额外信息才能完成转移？这种直觉是后续学习更复杂DP的基础。
接下来的方向大致有几个：一是状态压缩DP，把状态用二进制位表示，适合处理集合类问题；二是数位DP，处理数字的位上的约束；三是概率期望DP，处理带有随机性的问题；四是DP的各种优化技巧，比如单调队列优化、斜率优化、四边形不等式等。这些内容每一个都可以单独写一篇长文，但它们的根基都是初阶DP里那些最朴素的思想。
我个人的体会是，DP学习最忌讳的就是贪多求快。初阶阶段把线性DP、背包、区间DP、树形DP这四个基本模型练到滚瓜烂熟，比匆匆忙忙学一堆高级技巧但每个都一知半解要强得多。因为高级技巧本质上都是基本模型的变形和组合，基本模型不扎实，高级技巧就是空中楼阁。
最后分享一个我一直在用的小习惯：每做完一道DP题，在代码旁边用注释写下三句话——状态定义是什么、转移方程是什么、为什么这样定义状态。这个习惯看起来简单，但坚持下来，你会发现自己对DP的理解在不知不觉中变得非常清晰。等到某一天你拿到一道新题，能在五分钟内想清楚这三句话，那初阶DP这一关，你就真正过了。
