定义状态与转移
准确说明 dp[i] 的含义
定义状态与转移 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
动态规划的核心
每个动态规划问题都要先定义一个状态：dp[i] 实际表示什么？把这句话写准确，后面的内容就会顺理成章。
状态必须精确
用文字写出它的含义：dp[i] = 前 i 个项目的答案。含糊的状态定义会导致错误的递推关系。
dp[i] = best total using items 0..i-1状态转移
状态转移说明如何根据更早的状态构造 dp[i]。它是解法的核心递推方程。
dp[i] = dp[i-1] + dp[i-2]基础情况奠定基础
基础情况是您可以直接知道的最小状态。没有正确的起点，后续每个值都会逐渐偏离正确答案。
dp[0] = 1选择计算顺序
每个状态都必须在它所依赖的状态之后填充。这条依赖规则决定了循环方向。
for i in range(1, n+1): ...答案在哪里
请确定哪个单元格保存最终结果。它通常是dp[n]，但有时需要取整个表格中的最大值。
answer = dp[n] # or max(dp)统计状态数量
不同状态的数量决定您的时间预算。包含 n 个项目的一维 dp 有 O(n) 个状态需要填充。
每次转移的代价
总时间等于状态数量乘以每次转移的工作量。在 n 个状态中各执行一次 O(n) 转移，会得到 O(n^2)。
需要时增加一个维度
如果一个索引无法完整描述当前情况，就增加另一个索引。第二个维度会将 dp[i] 变为dp[i][j]。
dp = [[0]*(c+1) for _ in range(n+1)]重建选择
要恢复实际解，请记录每个状态中胜出的转移，然后从答案开始反向回溯。
choice[i] = "take"可复用的检查清单
状态、转移、边界条件、顺序、答案。确定这五点后，几乎任何 DP 递推式都能顺利构建出来。
快速检查
您正在设计一个 DP。dp[i] 表示什么？
回顾：先命名，再求解
现在您可以定义状态、写出状态转移、设置边界条件，并确定答案的位置。这份蓝图能让 DP 从凭感觉猜测变成按步骤解题。
常见问题解答
「定义状态与转移」课时是免费的吗？
是的 — 「定义状态与转移」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「定义状态与转移」这节课中我会学到什么？
准确说明 dp[i] 的含义 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「定义状态与转移」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。