查看“︁动态规划”︁的源代码

{{Multiple issues|
{{refimprove|time=2018-09-28T16:50:41+00:00}}
{{Expand language|1=en|time=2020-09-27T11:57:50+00:00}}
}}
{{NoteTA
|G1 = IT
}}
'''动态规划'''（{{lang-en|Dynamic programming}}，简称{{lang|en|DP}}）是一种在[[数学]]、[[管理科学]]、[[计算机科学]]、[[经济学]]和[[生物信息学]]中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题<ref>S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, ''''Algorithms'''', p 173, available at http://www.cs.berkeley.edu/~vazirani/algorithms.html {{Wayback|url=http://www.cs.berkeley.edu/~vazirani/algorithms.html |date=20131018100244 }}</ref>和{{Link-en|最优子结构|Optimal substructure}}性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其[[记忆化]]存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈[[指數增長]]时特别有用。

== 概述 ==
<!--撰写中，未完成-->
动态规划在查找有很多'''重叠子问题'''的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存[[递归]]时的结果，因而不会在解决同样的问题时花费不必要的时间。

动态规划只能应用于有'''最优子结构'''的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

解决动态规划问题时，我们需要按照以下步骤系统地思考和解决：

1. 定义状态：首先要思考如何用数学语言描述问题。定义状态是整个解题过程中最关键的一步，它决定了我们如何存储和使用计算结果。我们需要仔细思考：要解决的问题需要哪些变量来表示？这些状态通常会以数组的形式存储下来。一个好的状态定义应该能够完整地描述问题在某个阶段的情况。

2. 找出状态转移方程：当我们定义好状态后，需要思考状态之间是如何转移的。也就是说，如何从已知的状态推导出新的状态，状态转移方程是解决问题的核心，一般想明白状态转移方程问题就解决了。

3. 确定初始状态和边界条件：有了状态转移方程后，我们需要确定问题的初始状态。同时，我们还需要考虑一些特殊情况，比如输入为0或负数时应该如何处理。

4. 按照状态转移方程求解：最后一步是实际求解过程。我们通常会按照一定的顺序（比如从小到大）来计算每个状态的值。在这个过程中，我们使用已经计算出的状态值，通过状态转移方程来得到新的状态值。这个过程需要特别注意计算的顺序，确保在计算某个状态时，它依赖的所有状态都已经计算出来了。<ref>{{Cite web |url=https://gallery.selfboot.cn/zh/algorithms/dpcoin |title=动态规划硬币找零问题可视化 |access-date=2024-11-21 |archive-date=2025-01-22 |archive-url=https://web.archive.org/web/20250122040144/https://gallery.selfboot.cn/zh/algorithms/dpcoin |dead-url=no }}</ref>

== 适用情况 ==
# 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态規劃算法解决问题提供了重要线索。
# 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
# 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态規劃算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

== 实例 ==
包括但不限于切割钢条问题、Floyd最短路问题、最大不下降子序列、矩阵链乘、凸多边形三角剖分、背包问题、最长公共子序列、最优二分搜索树等。

==== 硬币找零问题 ====

'''硬币找零问题'''来自生活中的一个常见场景。给定一组不同面值的硬币，然后给定一个目标金额。我们的目标是计算出凑到目标金额所需的最少硬币数量。

我们可以定义状态 dp[i] 表示：凑出金额 i 所需的最少硬币数量。假设我们要计算dp[i]，也就是凑出金额 i 所需的最少硬币数，那么可以拆分为下面的子问题：

1. 如果我们选择使用了某个面值 m 的硬币，那么问题就转化为：凑出金额 (i-m) 所需的最少硬币数，再加上这一个新使用的硬币；

2. 由于我们要求的是最少硬币数，所以需要在所有可能的硬币选择中取最小值；

因此，状态转移方程如下，其中 m 遍历所有可用的硬币面值：dp[i] = min(dp[i-m] + 1).

可以在[https://gallery.selfboot.cn/zh/algorithms/dpcoin 动态规划之硬币找零可视化] {{Wayback|url=https://gallery.selfboot.cn/zh/algorithms/dpcoin |date=20250122040144 }}页面直观看到这里的求解过程。

==== 背包问题 ====
[[背包问题]]作为[[NP完全]]问题，暂时不存在[[多項式時間|多项式时间算法]]。动态规划属于背包问题求解最优解的可行方法之一。此外，求解背包问题最优解还有搜索法等，近似解还有[[贪心法]]等，分数背包问题有最优[[贪心算法|-{zh-hant:貪婪; zh-hans:贪心}-]]解等。
背包问题具有最优子结构和重叠子问题。动态规划一般用于求解背包问题中的整数背包问题（即每种物品所选的个数必须是整数）。
解整数背包问题：
设有<math> n </math>件物品，每件价值记为<math> P_i </math>，每件重量记为<math> W_i </math>，用一个最大重量为<math> W</math>的背包，求装入物品的最大价值。
在总重量不超过''W''的前提下，我们希望总价格最高。对于<math>Y\leqslant W</math>，我们将在总重量不超过<math>Y</math>的前提下，总价格所能达到的最高值定义为<math>A(Y)</math>。<math>A(W)</math>即为问题的答案。

显然，''A''(''Y'')满足：
* <math>A(0) = 0</math>
* <math>A(Y) = \max \{ A(Y - 1), p_j + A(Y - w_j) \}</math>
其中，<math>p_j</math>为第<math>j</math>种物品的价格。

对于特例01背包问题（即每件物品最多放1件，否则不放入）的问题，我们将在总重量不超过''Y''的前提下，前''j''种物品的总价格所能达到的最高值定义为''A''(''j'', ''Y'')。

''A''(''j'', ''Y'')的递推关系为：
* ''A''(0, ''Y'') = 0
* 如果''w<sub>j</sub>'' > ''Y'', ''A''(''j'', ''Y'') = ''A''(''j'' - 1, ''Y'')
* 如果''w<sub>j</sub>'' ≤ ''Y'', ''A''(''j'', ''Y'') = max { ''A''(''j'' - 1, ''Y''), ''p<sub>j</sub>'' + ''A''(''j'' - 1, ''Y'' - ''w<sub>j</sub>'')}

参考[[Pascal语言|Pascal]]代码
<syntaxhighlight lang="pascal">
for i:=1 to n do
  for v:=totv downto v[i] do
    f[v]:=max(f[v],f[v-v[i]]+p[i]);
writeln(f[totv]);
</syntaxhighlight>

参考[[C++]]代码（不含include和数组声明）
<syntaxhighlight lang="c++">
#define max(x,y) (x)>(y)?(x):(y) //max宏函数，也可以自己寫或者使用algorithm
for(int i=1;i<=n;i++)
  for (v=totv;v>=v[i];v--)
    f[v]=max(f[v],f[v-v[i]]+p[i]);
printf("%d",f[totv]); //或std::cout<<f[totv];
</syntaxhighlight>

== 历史 ==
术语“动态规划”最初是在1940年代由[[理查德·贝尔曼]]用来描述解决问题的过程，在这个过程中，人们需要一个接一个地找到最佳决策。到1953年，他将其精炼成为现代的含义，特别是指将较小的决策问题嵌套在较大的决策中，<ref>Stuart Dreyfus. [https://web.archive.org/web/20050110161049/http://www.wu-wien.ac.at/usr/h99c/h9951826/bellman_dynprog.pdf "Richard Bellman on the birth of Dynamical Programming"].</ref> 并且该领域随后被[[电气电子工程师学会]]认可为[[系统分析]]和[[工程学]]主题。贝尔曼的贡献以[[贝尔曼方程]]的名义被铭记，它是动态规划的核心结果，它以[[递归 (计算机科学)|递归]]形式重申了优化问题。

贝尔曼选择了“动态”这个词来捕捉问题的随时间变化的方面，也因为它听起来令人印象深刻。<ref name="Eddy">{{cite journal |last=Eddy |first=S. R. |author-link=Sean Eddy |title=What is Dynamic Programming? |url=https://archive.org/details/sim_nature-biotechnology_2004-07_22_7/page/909 |journal=Nature Biotechnology |volume=22 |issue= 7|pages=909–910 |year=2004 |doi=10.1038/nbt0704-909 |pmid=15229554 |s2cid=5352062 }}</ref> “规划”一词指的是使用该方法来找到最佳的“程序”，在于军事训练或后勤计划的意义。这种用法与短语“[[线性规划]]”和“[[数学规划]]”中的用法相同。<ref>{{cite book |last1=Nocedal |first1=J. |last2=Wright |first2=S. J. |title=Numerical Optimization |url=https://archive.org/details/numericaloptimiz00noce_639 |url-access=limited |page=[https://archive.org/details/numericaloptimiz00noce_639/page/n21 9] |publisher=Springer |year=2006 |isbn=9780387303031 }}</ref>

术语起源的上述解释是不足的。正如罗素和诺维格在他们的书中提到上述故事时所写的那样：“这不可能完全正确，因为他的第一篇使用这个词（贝尔曼，1952）的论文出现在威尔逊于 1953 年成为国防部长之前。”<ref>{{cite book |last1=Russell |first1=S. |last2=Norvig |first2=P. |title=Artificial Intelligence: A Modern Approach |edition=3rd |publisher=Prentice Hall |year=2009 |isbn=978-0-13-207148-2 }}</ref>此外，还有[http://a2c2.org/awards/richard-e-bellman-control-heritage-award/2004-00-00t000000/harold-j-kushner Harold J. Kushner] {{Wayback|url=http://a2c2.org/awards/richard-e-bellman-control-heritage-award/2004-00-00t000000/harold-j-kushner |date=20170301091951 }}在演讲中的评论，他记得贝尔曼。他在谈到贝尔曼时引用库什纳的话：“另一方面，当我问他同样的问题时，他回答说他试图通过加上动态来超越[[乔治·伯纳德·丹齐格]]的线性规划。也许这两种动机都是正确的。”

== 使用动态规划的算法 ==
* [[最长公共子序列]]
* [[Floyd-Warshall算法]]
* [[维特比算法|Viterbi算法]]
* [[Kadane's_algorithm]]<ref>{{cite book |title=Maximum_subarray_problem |url=https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm |access-date=2023-01-18 |archive-date=2023-02-04 |archive-url=https://web.archive.org/web/20230204084130/https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm |dead-url=no }}</ref>
* 求解[[馬可夫決策過程]]下最佳策略<ref>{{cite book |author1=Richard S. Sutton |author2=Andrew G. Barto |title=Reinforcement Learning: An Introduction |date=2018 |publisher=The MIT Press |page=73 |edition=Second Edition |url=http://incompleteideas.net/book/the-book-2nd.html |access-date=2020-08-22 |archive-date=2022-01-18 |archive-url=https://web.archive.org/web/20220118121938/http://incompleteideas.net/book/the-book-2nd.html |dead-url=no }}</ref>
* [[萊文斯坦距離]]

== 参考 ==
<references/>

== 外部链接 ==

{{算法}}
{{Authority control}}
[[Category:动态规划| ]]
[[Category:最优化算法]]