1. 项目概述从“最优解”到“具体路径”在算法竞赛和面试准备中我们常常会遇到一类经典问题背包问题。无论是AcWing、LeetCode还是其他OJ平台背包问题都是动态规划入门的必修课。我们学会了如何用状态转移方程f[i][j] max(f[i-1][j], f[i-1][j-v[i]] w[i])计算出在容量为j的背包中从前i个物品里能获取的最大价值。这个“最大价值”是一个数字它告诉我们“最好能拿多少”但很多时候面试官或题目会进一步追问“那么具体是选了哪些物品才达到这个最大价值的呢”这就是“背包问题求具体方案”的核心。它不再是简单地求一个最优值而是要求我们回溯出构成这个最优值的决策路径。这就像你知道从A地到B地的最短距离是100公里但考官现在要你画出具体的路线图。理解如何从动态规划表中“倒推”出具体方案不仅是对01背包问题的深度掌握更是理解动态规划“状态”与“决策”之间关系的关键一步对于解决其他需要输出方案的问题如最长公共子序列的输出、最短路径的打印等具有举足轻重的意义。2. 核心思路解析状态定义与倒推的艺术求具体方案核心在于我们当初是如何定义动态规划状态的。最常见的状态定义是f[i][j]表示只考虑前i个物品物品编号从1到i在背包容量恰好为j的情况下能获得的最大价值。注意这里“只考虑前i个物品”意味着决策到了第i个物品为止。当我们计算出最终的答案f[N][V]N为物品总数V为背包总容量后如何知道第N个物品是否被选中了呢答案就藏在状态转移的过程中如果f[N][V] f[N-1][V]这说明达到最大价值时没有选择第N个物品。因为不考虑第N个物品只考虑前N-1个也能达到同样的价值。如果f[N][V] f[N-1][V - v[N]] w[N]并且V v[N]这说明达到最大价值时选择了第N个物品。因为当前价值等于“没选它之前的状态”加上它的价值。因此求具体方案的基本思路就是倒序回溯从最终状态f[N][V]出发根据状态转移方程逆向判断每个物品是否被选中并更新当前考察的容量一直回溯到第一个物品。这里有一个至关重要的细节字典序最小的方案。题目常常要求在有多个最优方案时输出物品编号字典序最小的那个。什么是字典序最小简单说就是能选编号小的物品就尽量先选。为了实现这一点我们不能简单地从N倒推到1因为那样得到的方案是“逆序”的例如输出{3, 1}且不一定是字典序最小。关键技巧为了输出字典序最小的方案我们需要在动态规划阶段就为倒序回溯做好准备。具体做法是在计算f[i][j]时改变物品的遍历和决策顺序。通常我们正序从1到N遍历物品计算f[i][j]。但为了便于后续按字典序输出我们可以倒序从N到1遍历物品来定义状态。即定义f[i][j]为只考虑后i个物品从第i个物品到第N个物品容量为j时的最大价值。这样最终答案是f[1][V]。回溯时我们从第1个物品编号最小开始正序判断就自然满足了“能选编号小的就选”的字典序要求。3. 算法步骤拆解与代码实现下面我们以经典的01背包问题为例详细拆解求字典序最小具体方案的完整步骤。假设有 N 个物品背包容量为 V第 i 个物品的体积是v[i]价值是w[i]。3.1 状态定义与转移方程倒序物品版我们重新定义状态数组f[i][j]表示只考虑从第i个物品到第N个物品即后缀物品序列在背包容量为j的情况下能获得的最大价值。状态转移方程与标准01背包类似只是物品索引的含义变了不选第 i 个物品f[i][j] f[i1][j]选第 i 个物品前提是j v[i]f[i][j] f[i1][j - v[i]] w[i]最终f[i][j]取两者的最大值f[i][j] max(f[i1][j], f[i1][j-v[i]] w[i])这里f[i1][*]代表考虑第 i1 到第 N 个物品的状态符合我们“从后向前考虑”的定义。3.2 动态规划填表过程我们需要从后往前i 从 N 递减到 1计算这个二维表。初始化时f[N1][j] 0表示没有物品可选时价值为0。#include iostream #include algorithm using namespace std; const int MAXN 1010, MAXV 1010; int v[MAXN], w[MAXN]; int f[MAXN][MAXV]; // f[i][j] 定义如上 int main() { int N, V; cin N V; for (int i 1; i N; i) cin v[i] w[i]; // 倒序填充动态规划表 for (int i N; i 1; --i) { for (int j 0; j V; j) { f[i][j] f[i1][j]; // 不选物品i if (j v[i]) { f[i][j] max(f[i][j], f[i1][j - v[i]] w[i]); } } } // 最大价值存储在 f[1][V] 中 // cout f[1][V] endl; // 如果题目只要求价值这里输出即可 }3.3 回溯构造具体方案现在我们有了填好的表f[][]最大价值是f[1][V]。我们从i 1, j V开始回溯目的是判断每个物品是否被选中。回溯逻辑初始化当前容量cur_v V。正序遍历物品i从 1 到 N如果cur_v v[i]且f[i][cur_v] f[i1][cur_v - v[i]] w[i]那么说明在最优方案中选择了物品 i。输出物品 i或将其存入结果数组。更新当前容量cur_v - v[i]。否则说明没有选物品 i。cur_v保持不变。遍历完成后输出的物品编号序列即为字典序最小的具体方案。注意事项判断条件f[i][cur_v] f[i1][cur_v - v[i]] w[i]是核心。必须同时满足“容量足够”和“价值相等”两个条件才能推断出选择了该物品。这里用“”是因为状态转移时我们用了max如果选了物品i能达到最大值那么等式必然成立。特别注意当f[i][cur_v]同时等于“不选”和“选”两种情况的价值时即两者相等根据字典序最小要求我们应该优先选择这个物品因为我们要让编号小的物品尽可能被选。上述判断逻辑恰好满足了这一点因为它优先检查了“选择”是否成立。// 接续上面的动态规划代码 int cur_v V; for (int i 1; i N; i) { // 关键判断如果当前容量能装下物品i并且选择i能达到当前最优值 if (cur_v v[i] f[i][cur_v] f[i1][cur_v - v[i]] w[i]) { cout i ; // 输出选择了物品i cur_v - v[i]; // 更新剩余容量 } }3.4 完整代码示例AcWing 12. 风格将以上两部分结合并处理输入输出就得到了AcWing 12.题目的标准解答。#include iostream #include algorithm using namespace std; const int N 1010; int v[N], w[N]; int f[N][N]; int main() { int n, m; cin n m; for (int i 1; i n; i) cin v[i] w[i]; // 倒序DP for (int i n; i 1; i--) { for (int j 0; j m; j) { f[i][j] f[i 1][j]; if (j v[i]) f[i][j] max(f[i][j], f[i 1][j - v[i]] w[i]); } } // 回溯找方案 int j m; for (int i 1; i n; i) { // 判断时由于我们要字典序最小所以当“选”和“不选”价值相等时我们优先选即输出 if (j v[i] f[i][j] f[i 1][j - v[i]] w[i]) { cout i ; j - v[i]; } } return 0; }4. 深度剖析为什么倒序遍历物品能求字典序方案这是本问题的精髓所在也是容易混淆的点。我们来彻底理清其中的逻辑。1. 标准做法正序DP逆序回溯的问题我们通常定义f[i][j]为考虑前i个物品。计算顺序i从1到N。最终状态f[N][V]。回溯从iN, jV开始判断f[i][j]是否等于f[i-1][j-v[i]]w[i]。如果相等说明选了物品i但此时i是大的编号。输出顺序回溯得到的物品序列是逆序的例如{3, 1}。要得到正序需要反转数组。字典序问题更严重的是当存在多个最优方案时这种从后往前回溯的方式无法保证输出的是编号字典序最小的方案。因为它总是先决策最后一个物品其选择策略并不是“优先选编号小的”。2. 改进做法倒序DP正序回溯的巧妙之处状态定义f[i][j]为考虑从第i个到第N个物品。计算顺序i从N向下到1。这相当于我们在计算时是“从未来向过去”计算。f[i][j]的值依赖于“更未来”的状态f[i1][*]。最终状态f[1][V]。它表示考虑从第1个到第N个物品即所有物品的最大价值。回溯我们从i1, jV开始。此时我们面对的是第一个物品编号最小。我们的判断依据是当前状态f[1][V]是否是通过选择物品1达到的即判断f[1][V] f[2][V-v[1]] w[1]是否成立。字典序的保证这个判断发生在决策的最前端。如果成立我们立刻输出物品1。这完美实现了“能选编号小的物品就优先选”的贪心策略。然后我们带着剩余的容量去决策下一个物品i2。这个过程是正序的每一步都优先考虑当前编号最小的物品是否可选从而自然得到了字典序最小的方案。一个生动的比喻想象你要从一堆礼物中选一些放进箱子要求总价值最大并且如果有多组方案你希望选到的礼物编号列表看起来尽可能“小”比如选1,3,5而不是2,4,5。错误方法正序DP逆序回溯你先计划好所有选择然后从最后选的礼物开始往外说。你最后决定的那个礼物编号可能很大会最先被说出来这不利于生成一个“开头数字小”的列表。正确方法倒序DP正序回溯你从礼物堆的另一端开始规划。你站在编号为1的礼物前先问自己“如果我从现在开始做最优选择我会拿这个1号礼物吗” 你的决策依据是“拿了它之后后面剩下的礼物能不能组成一个最优计划”。如果是你就拿上它。这样你总是先决定编号最小的礼物的命运最终说出的列表自然就是字典序最小的。5. 常见问题、调试技巧与扩展5.1 常见错误与排查数组越界在回溯判断时务必先检查j v[i]再访问f[i1][j - v[i]]否则会访问非法内存。状态转移方程写错特别注意倒序DP时f[i][j]的初始值应来自f[i1][j]而不是f[i-1][j]。这是最容易出错的地方。字典序理解偏差字典序最小不是指物品体积或价值的顺序而是物品编号的序列。例如方案{1, 3, 5}的字典序就小于{1, 4, 5}因为第二位34。方案不唯一时的处理我们的代码通过if (j v[i] f[i][j] f[i1][j - v[i]] w[i])这个条件在“选”与“不选”价值相等时优先执行了“选”的分支从而保证了字典序最小。如果题目要求输出所有方案则需要用DFS进行回溯搜索。5.2 空间优化与方案记录上述代码使用了O(N*V)的二维数组。实际上01背包的状态可以优化到一维。但求具体方案时通常不能使用滚动数组优化因为我们需要完整的二维DP表来进行回溯知道每个(i, j)状态是从哪里转移来的。如果压缩到一维就会丢失物品维度的信息无法回溯。如果非要在空间紧张的情况下尝试一种思路是额外用一个二维布尔数组g[i][j]来记录在状态(i, j)下是否选择了物品 i。这样DP过程可以用滚动数组但同时更新g数组。回溯时根据g数组来推断。但这实际上并没有减少空间复杂度g数组也是O(N*V)只是提供了一种不同的记录思路。5.3 扩展到完全背包与多重背包完全背包每个物品无限个。其状态转移方程为f[i][j] max(f[i-1][j], f[i][j-v[i]] w[i])。求具体方案时回溯逻辑需要改变。因为f[i][j]可能从f[i][j-v[i]]转移而来这意味着物品i可能被选了多次。回溯时需要用一个循环当f[i][j] f[i][j - v[i]] w[i]时持续输出物品i并减小j直到条件不成立再i--。多重背包每个物品有固定数量s[i]。通常转化为01背包或使用二进制优化。求方案时如果转化成了01背包则方法同01背包如果直接用多重背包的状态转移回溯会非常复杂通常也需要记录决策路径。5.4 实战心得与技巧先写标准再改倒序如果不确定可以先写出标准01背包求最大价值的代码。然后将遍历i的循环反过来并将所有i-1改为i1将f[N][V]改为f[1][V]。这样重构不容易出错。手动模拟小数据对于不确定的算法最好的调试方法是找一组很小的数据如N3, V5在纸上画出二维DP表手动执行一遍倒序DP和正序回溯的过程。这是理解算法最有效的方式。理解本质求具体方案的本质是动态规划的反向查询。DP表记录的是所有子问题的解我们就像查地图一样从终点反推回起点。定义状态的方式决定了这张“地图”的索引因此想要方便地按字典序查询就需要在“绘图”DP时采用合适的坐标系倒序定义状态。适用性这套“倒序DP正序回溯”的方法可以推广到任何需要输出字典序最小方案的动态规划问题。核心思想就是让DP的计算顺序与最终方案的选择顺序相反从而在回溯时能够从字典序的起点开始做贪心选择。掌握背包问题求具体方案尤其是处理字典序要求是你动态规划能力从“会算”到“精通”的一个重要标志。它强迫你去深入理解状态定义的每一个细节以及状态之间是如何关联和转移的。下次再遇到需要输出方案的问题不妨先想想我的状态定义方便我回溯出想要的答案吗 动态规划进阶：01背包问题求字典序最小具体方案详解
1. 项目概述从“最优解”到“具体路径”在算法竞赛和面试准备中我们常常会遇到一类经典问题背包问题。无论是AcWing、LeetCode还是其他OJ平台背包问题都是动态规划入门的必修课。我们学会了如何用状态转移方程f[i][j] max(f[i-1][j], f[i-1][j-v[i]] w[i])计算出在容量为j的背包中从前i个物品里能获取的最大价值。这个“最大价值”是一个数字它告诉我们“最好能拿多少”但很多时候面试官或题目会进一步追问“那么具体是选了哪些物品才达到这个最大价值的呢”这就是“背包问题求具体方案”的核心。它不再是简单地求一个最优值而是要求我们回溯出构成这个最优值的决策路径。这就像你知道从A地到B地的最短距离是100公里但考官现在要你画出具体的路线图。理解如何从动态规划表中“倒推”出具体方案不仅是对01背包问题的深度掌握更是理解动态规划“状态”与“决策”之间关系的关键一步对于解决其他需要输出方案的问题如最长公共子序列的输出、最短路径的打印等具有举足轻重的意义。2. 核心思路解析状态定义与倒推的艺术求具体方案核心在于我们当初是如何定义动态规划状态的。最常见的状态定义是f[i][j]表示只考虑前i个物品物品编号从1到i在背包容量恰好为j的情况下能获得的最大价值。注意这里“只考虑前i个物品”意味着决策到了第i个物品为止。当我们计算出最终的答案f[N][V]N为物品总数V为背包总容量后如何知道第N个物品是否被选中了呢答案就藏在状态转移的过程中如果f[N][V] f[N-1][V]这说明达到最大价值时没有选择第N个物品。因为不考虑第N个物品只考虑前N-1个也能达到同样的价值。如果f[N][V] f[N-1][V - v[N]] w[N]并且V v[N]这说明达到最大价值时选择了第N个物品。因为当前价值等于“没选它之前的状态”加上它的价值。因此求具体方案的基本思路就是倒序回溯从最终状态f[N][V]出发根据状态转移方程逆向判断每个物品是否被选中并更新当前考察的容量一直回溯到第一个物品。这里有一个至关重要的细节字典序最小的方案。题目常常要求在有多个最优方案时输出物品编号字典序最小的那个。什么是字典序最小简单说就是能选编号小的物品就尽量先选。为了实现这一点我们不能简单地从N倒推到1因为那样得到的方案是“逆序”的例如输出{3, 1}且不一定是字典序最小。关键技巧为了输出字典序最小的方案我们需要在动态规划阶段就为倒序回溯做好准备。具体做法是在计算f[i][j]时改变物品的遍历和决策顺序。通常我们正序从1到N遍历物品计算f[i][j]。但为了便于后续按字典序输出我们可以倒序从N到1遍历物品来定义状态。即定义f[i][j]为只考虑后i个物品从第i个物品到第N个物品容量为j时的最大价值。这样最终答案是f[1][V]。回溯时我们从第1个物品编号最小开始正序判断就自然满足了“能选编号小的就选”的字典序要求。3. 算法步骤拆解与代码实现下面我们以经典的01背包问题为例详细拆解求字典序最小具体方案的完整步骤。假设有 N 个物品背包容量为 V第 i 个物品的体积是v[i]价值是w[i]。3.1 状态定义与转移方程倒序物品版我们重新定义状态数组f[i][j]表示只考虑从第i个物品到第N个物品即后缀物品序列在背包容量为j的情况下能获得的最大价值。状态转移方程与标准01背包类似只是物品索引的含义变了不选第 i 个物品f[i][j] f[i1][j]选第 i 个物品前提是j v[i]f[i][j] f[i1][j - v[i]] w[i]最终f[i][j]取两者的最大值f[i][j] max(f[i1][j], f[i1][j-v[i]] w[i])这里f[i1][*]代表考虑第 i1 到第 N 个物品的状态符合我们“从后向前考虑”的定义。3.2 动态规划填表过程我们需要从后往前i 从 N 递减到 1计算这个二维表。初始化时f[N1][j] 0表示没有物品可选时价值为0。#include iostream #include algorithm using namespace std; const int MAXN 1010, MAXV 1010; int v[MAXN], w[MAXN]; int f[MAXN][MAXV]; // f[i][j] 定义如上 int main() { int N, V; cin N V; for (int i 1; i N; i) cin v[i] w[i]; // 倒序填充动态规划表 for (int i N; i 1; --i) { for (int j 0; j V; j) { f[i][j] f[i1][j]; // 不选物品i if (j v[i]) { f[i][j] max(f[i][j], f[i1][j - v[i]] w[i]); } } } // 最大价值存储在 f[1][V] 中 // cout f[1][V] endl; // 如果题目只要求价值这里输出即可 }3.3 回溯构造具体方案现在我们有了填好的表f[][]最大价值是f[1][V]。我们从i 1, j V开始回溯目的是判断每个物品是否被选中。回溯逻辑初始化当前容量cur_v V。正序遍历物品i从 1 到 N如果cur_v v[i]且f[i][cur_v] f[i1][cur_v - v[i]] w[i]那么说明在最优方案中选择了物品 i。输出物品 i或将其存入结果数组。更新当前容量cur_v - v[i]。否则说明没有选物品 i。cur_v保持不变。遍历完成后输出的物品编号序列即为字典序最小的具体方案。注意事项判断条件f[i][cur_v] f[i1][cur_v - v[i]] w[i]是核心。必须同时满足“容量足够”和“价值相等”两个条件才能推断出选择了该物品。这里用“”是因为状态转移时我们用了max如果选了物品i能达到最大值那么等式必然成立。特别注意当f[i][cur_v]同时等于“不选”和“选”两种情况的价值时即两者相等根据字典序最小要求我们应该优先选择这个物品因为我们要让编号小的物品尽可能被选。上述判断逻辑恰好满足了这一点因为它优先检查了“选择”是否成立。// 接续上面的动态规划代码 int cur_v V; for (int i 1; i N; i) { // 关键判断如果当前容量能装下物品i并且选择i能达到当前最优值 if (cur_v v[i] f[i][cur_v] f[i1][cur_v - v[i]] w[i]) { cout i ; // 输出选择了物品i cur_v - v[i]; // 更新剩余容量 } }3.4 完整代码示例AcWing 12. 风格将以上两部分结合并处理输入输出就得到了AcWing 12.题目的标准解答。#include iostream #include algorithm using namespace std; const int N 1010; int v[N], w[N]; int f[N][N]; int main() { int n, m; cin n m; for (int i 1; i n; i) cin v[i] w[i]; // 倒序DP for (int i n; i 1; i--) { for (int j 0; j m; j) { f[i][j] f[i 1][j]; if (j v[i]) f[i][j] max(f[i][j], f[i 1][j - v[i]] w[i]); } } // 回溯找方案 int j m; for (int i 1; i n; i) { // 判断时由于我们要字典序最小所以当“选”和“不选”价值相等时我们优先选即输出 if (j v[i] f[i][j] f[i 1][j - v[i]] w[i]) { cout i ; j - v[i]; } } return 0; }4. 深度剖析为什么倒序遍历物品能求字典序方案这是本问题的精髓所在也是容易混淆的点。我们来彻底理清其中的逻辑。1. 标准做法正序DP逆序回溯的问题我们通常定义f[i][j]为考虑前i个物品。计算顺序i从1到N。最终状态f[N][V]。回溯从iN, jV开始判断f[i][j]是否等于f[i-1][j-v[i]]w[i]。如果相等说明选了物品i但此时i是大的编号。输出顺序回溯得到的物品序列是逆序的例如{3, 1}。要得到正序需要反转数组。字典序问题更严重的是当存在多个最优方案时这种从后往前回溯的方式无法保证输出的是编号字典序最小的方案。因为它总是先决策最后一个物品其选择策略并不是“优先选编号小的”。2. 改进做法倒序DP正序回溯的巧妙之处状态定义f[i][j]为考虑从第i个到第N个物品。计算顺序i从N向下到1。这相当于我们在计算时是“从未来向过去”计算。f[i][j]的值依赖于“更未来”的状态f[i1][*]。最终状态f[1][V]。它表示考虑从第1个到第N个物品即所有物品的最大价值。回溯我们从i1, jV开始。此时我们面对的是第一个物品编号最小。我们的判断依据是当前状态f[1][V]是否是通过选择物品1达到的即判断f[1][V] f[2][V-v[1]] w[1]是否成立。字典序的保证这个判断发生在决策的最前端。如果成立我们立刻输出物品1。这完美实现了“能选编号小的物品就优先选”的贪心策略。然后我们带着剩余的容量去决策下一个物品i2。这个过程是正序的每一步都优先考虑当前编号最小的物品是否可选从而自然得到了字典序最小的方案。一个生动的比喻想象你要从一堆礼物中选一些放进箱子要求总价值最大并且如果有多组方案你希望选到的礼物编号列表看起来尽可能“小”比如选1,3,5而不是2,4,5。错误方法正序DP逆序回溯你先计划好所有选择然后从最后选的礼物开始往外说。你最后决定的那个礼物编号可能很大会最先被说出来这不利于生成一个“开头数字小”的列表。正确方法倒序DP正序回溯你从礼物堆的另一端开始规划。你站在编号为1的礼物前先问自己“如果我从现在开始做最优选择我会拿这个1号礼物吗” 你的决策依据是“拿了它之后后面剩下的礼物能不能组成一个最优计划”。如果是你就拿上它。这样你总是先决定编号最小的礼物的命运最终说出的列表自然就是字典序最小的。5. 常见问题、调试技巧与扩展5.1 常见错误与排查数组越界在回溯判断时务必先检查j v[i]再访问f[i1][j - v[i]]否则会访问非法内存。状态转移方程写错特别注意倒序DP时f[i][j]的初始值应来自f[i1][j]而不是f[i-1][j]。这是最容易出错的地方。字典序理解偏差字典序最小不是指物品体积或价值的顺序而是物品编号的序列。例如方案{1, 3, 5}的字典序就小于{1, 4, 5}因为第二位34。方案不唯一时的处理我们的代码通过if (j v[i] f[i][j] f[i1][j - v[i]] w[i])这个条件在“选”与“不选”价值相等时优先执行了“选”的分支从而保证了字典序最小。如果题目要求输出所有方案则需要用DFS进行回溯搜索。5.2 空间优化与方案记录上述代码使用了O(N*V)的二维数组。实际上01背包的状态可以优化到一维。但求具体方案时通常不能使用滚动数组优化因为我们需要完整的二维DP表来进行回溯知道每个(i, j)状态是从哪里转移来的。如果压缩到一维就会丢失物品维度的信息无法回溯。如果非要在空间紧张的情况下尝试一种思路是额外用一个二维布尔数组g[i][j]来记录在状态(i, j)下是否选择了物品 i。这样DP过程可以用滚动数组但同时更新g数组。回溯时根据g数组来推断。但这实际上并没有减少空间复杂度g数组也是O(N*V)只是提供了一种不同的记录思路。5.3 扩展到完全背包与多重背包完全背包每个物品无限个。其状态转移方程为f[i][j] max(f[i-1][j], f[i][j-v[i]] w[i])。求具体方案时回溯逻辑需要改变。因为f[i][j]可能从f[i][j-v[i]]转移而来这意味着物品i可能被选了多次。回溯时需要用一个循环当f[i][j] f[i][j - v[i]] w[i]时持续输出物品i并减小j直到条件不成立再i--。多重背包每个物品有固定数量s[i]。通常转化为01背包或使用二进制优化。求方案时如果转化成了01背包则方法同01背包如果直接用多重背包的状态转移回溯会非常复杂通常也需要记录决策路径。5.4 实战心得与技巧先写标准再改倒序如果不确定可以先写出标准01背包求最大价值的代码。然后将遍历i的循环反过来并将所有i-1改为i1将f[N][V]改为f[1][V]。这样重构不容易出错。手动模拟小数据对于不确定的算法最好的调试方法是找一组很小的数据如N3, V5在纸上画出二维DP表手动执行一遍倒序DP和正序回溯的过程。这是理解算法最有效的方式。理解本质求具体方案的本质是动态规划的反向查询。DP表记录的是所有子问题的解我们就像查地图一样从终点反推回起点。定义状态的方式决定了这张“地图”的索引因此想要方便地按字典序查询就需要在“绘图”DP时采用合适的坐标系倒序定义状态。适用性这套“倒序DP正序回溯”的方法可以推广到任何需要输出字典序最小方案的动态规划问题。核心思想就是让DP的计算顺序与最终方案的选择顺序相反从而在回溯时能够从字典序的起点开始做贪心选择。掌握背包问题求具体方案尤其是处理字典序要求是你动态规划能力从“会算”到“精通”的一个重要标志。它强迫你去深入理解状态定义的每一个细节以及状态之间是如何关联和转移的。下次再遇到需要输出方案的问题不妨先想想我的状态定义方便我回溯出想要的答案吗