对一类动态规划问题的研究
湖南省长沙市第一中学 徐源盛
【关键字】
动态规划 费用提前计算 假设未来决策
【摘要】
本文通过四道题目探讨了一种比较特殊的动态规划问题，即当前决策影响未
来“行动”的费用。如果当前决策对未来的影响只与当前决策有关，则直接将对
未来费用的影响，算作当前的决策费用计算，并通过状态传递；如果对未来的影
响还与未来的情况有关，则新增状态假设未来的情况，待到未来决策时直接使用
假设的状态。这就是本论文详细阐述的解题方法。
【正文】
在常规动态规划问题中，我们面临当前状态时“行动”造成的花费往往与这个
状 态 是 同 时 计 算 的 。 例 如 在 经 典 的 石 子 合 并 问 题 中 ， 规 划 方 程 为
f[i][j]=max{f[i][k]+f[k+1][j]}+w(i,j)，当我们计算 f[i][j]时，才会把将 i 到 j 的石子全部
合并到一起这一“行动”的费用加进去。这很符合我们的思维习惯。
然而近年来频繁出现一类动态规划问题，在这类问题中，当前“行动”的费用
的一部分需要在之前决策时被计算并以状态的形式对当前状态造成影响。造成这
一独特的计算的原因就是当前的决策会对未来的“行动”费用造成影响。这类问题
构造方程往往比较困难，需要仔细分析原题，找到矛盾所在。
一、 当前决策对未来“行动”的费用影响只与当前决策有关
比如在两男两女中选一男一女去执行任务，已知每个人的效率，希望总效率
最高。并且男 A 如果被选，所有女生的效率加 7，如果男 B 被选，所有女生的效
率减 7。在第一阶段选男 A 还是男 B 对第二阶段女生的效率有不同的影响，可以
将对女生的影响当做男生的“自身魅力”，即把男 A 的效率加 7，男 B 的效率减
7。而我们实际上是把第二阶段的费用在第一阶段计算了。对于这类问题我们往
往将对未来“行动”的影响一并算做当前决策的费用。下面通过两道例题进行详细
阐述。
【问题一】Sue 的小球(sdtsc 2008)
Sue 和 Sandy 最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且
充满刺激的大海上。Sue 有一支轻便小巧的小船，然而，Sue 的目标并不是当一
