动态规划的实现问题

1. 动态规划的实现问题

算法实现是比较好考虑的。但有时也会遇到一些问题，而使算法难以实现。动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率往往是比较高的，这样在时间上溢出的可能性不大，而相反地，动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。另一方面，动态规划的高时效性往往要通过大的测试数据体现出来（以与搜索作比较），因而，对于大规模的问题如何在基本不影响运行速度的条件下，解决空间溢出的问题，是动态规划解决问题时一个普遍会遇到的问题。一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑，仅仅存储必不可少的内容，以及数据存储范围上精打细算(按位存储、压缩存储等)。当然这要因问题而异，进行分析。另外，在实现动态规划时，一个我们经常采用的方法是用一个与结点数一样多的数组来存储每一步的决策，这对于倒推求得一种实现最优解的方法是十分方便的，而且处理速度也有一些提高。但是在内存空间紧张的情况下，我们就应该抓住问题的主要矛盾。省去这个存储决策的数组，而改成在从最优解逐级倒推时，再计算一次，选择某个可能达到这个值的上一阶段的状态，直到推出结果为止。这样做，在程序编写上比上一种做法稍微多花一点时间，运行的时效也可能会有一些(但往往很小)的下降，但却换来了很多的空间。因而这种思想在处理某些问题时，是很有意义的。但有时，即使采用这样的方法也会发现空间溢出的问题。这时就要分析，这些保留下来的数据是否有必要同时存在于内存之中。因为有很多问题，动态规划递推在处理后面的内容时，前面比较远处的内容实际上是用不着的。对于这类问题，在已经确信不会再被使用的数据上覆盖数据，从而使空间得以重复利用，如果能有效地使用这一手段，对于相当大规模的问题，空间也不至于溢出（为了求出最优方案，保留每一步的决策仍是必要的，这同样需要空间）。一般地说，这种方法可以通过两种思路来实现：一种是递推结果仅使用Data1和Data2这样两个数组，每次将Data1作为上一阶段，推得Data2数组，然后，将Data2通过复制覆盖到Data1之上，如此反复，即可推得最终结果。这种做法有一个局限性，就是对于递推与前面若干阶段相关的问题，这种做法就比较麻烦；而且，每递推一级，就需要复制很多的内容，与前面多个阶段相关的问题影响更大。另外一种实现方法是，对于一个可能与前N个阶段相关的问题，建立数组Data[0..N]，其中各项为前面N个阶段的保存数据。这样不采用这种内存节约方式时对于阶段k的访问只要对应成对数组Data中下标为k mod (N+1)的单元的访问就可以了。这种处理方法对于程序修改的代码很少，速度几乎不受影响，而且需要保留不同的阶段数也都能很容易实现。当采用以上方法仍无法解决内存问题时，也可以采用对内存的动态申请来使绝大多数情况能有效出解。而且，使用动态内存还有一点好处，就是在重复使用内存而进行交换时，可以只对指针进行交换，而不复制数据，这在实践中也是十分有效的。

2. 什么是动态规划？动态规划的意义是什么？

动态规划中递推式的求解方法不是动态规划的本质。

我曾经作为省队成员参加过NOI，保送之后也给学校参加NOIP的同学多次讲过动态规划，我试着讲一下我理解的动态规划，争取深入浅出。希望你看了我的答案，能够喜欢上动态规划。

0. 动态规划的本质，是对问题状态的定义和状态转移方程的定义。
引自维基百科
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
本题下的其他答案，大多都是在说递推的求解方法，但如何拆分问题，才是动态规划的核心。
而拆分问题，靠的就是状态的定义和状态转移方程的定义。

1. 什么是状态的定义？

首先想说大家千万不要被下面的数学式吓到，这里只涉及到了函数相关的知识。
我们先来看一个动态规划的教学必备题：
给定一个数列，长度为N，
求这个数列的最长上升（递增）子数列（LIS）的长度.
以
1 7 2 8 3 4
为例。
这个数列的最长递增子数列是 1 2 3 4，长度为4；
次长的长度为3， 包括 1 7 8; 1 2 3 等.要解决这个问题，我们首先要定义这个问题和这个问题的子问题。
有人可能会问了，题目都已经在这了，我们还需定义这个问题吗？需要，原因就是这个问题在字面上看，找不出子问题，而没有子问题，这个题目就没办法解决。

所以我们来重新定义这个问题：
给定一个数列，长度为N，
设为：以数列中第k项结尾的最长递增子序列的长度.
求 中的最大值.显然，这个新问题与原问题等价。
而对于来讲，都是的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第中某项结尾的LIS。

上述的新问题也可以叫做状态，定义中的“为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。
之所以把做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。


对状态的定义只有一种吗？当然不是。
我们甚至可以二维的，以完全不同的视角定义这个问题：
给定一个数列，长度为N，
设为：
在前i项中的，长度为k的最长递增子序列中，最后一位的最小值. .
若在前i项中，不存在长度为k的最长递增子序列，则为正无穷.
求最大的x，使得不为正无穷。这个新定义与原问题的等价性也不难证明，请读者体会一下。
上述的就是状态，定义中的“为：在前i项中，长度为k的最长递增子序列中，最后一位的最小值”就是对状态的定义。


2. 什么是状态转移方程？
上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。

比如，对于LIS问题，我们的第一种定义：
设为：以数列中第k项结尾的最长递增子序列的长度.设A为题中数列，状态转移方程为：
 （根据状态定义导出边界情况）
用文字解释一下是：
以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。

第二种定义：
设为：在数列前i项中，长度为k的递增子序列中，最后一位的最小值设A为题中数列，状态转移方程为：
若则
否则：（边界情况需要分类讨论较多，在此不列出，需要根据状态定义导出边界情况。）
大家套着定义读一下公式就可以了，应该不难理解，就是有点绕。

这里可以看出，这里的状态转移方程，就是定义了问题和子问题之间的关系。
可以看出，状态转移方程就是带有条件的递推式。

3. 动态规划迷思
本题下其他用户的回答跟动态规划都有或多或少的联系，我也讲一下与本答案的联系。

a. “缓存”，“重叠子问题”，“记忆化”：
这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。
上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，不是动态规划的核心。

b. “递归”：
递归是递推式求解的方法，连技巧都算不上。

c. "无后效性"，“最优子结构”：
上述的状态转移方程中，等式右边不会用到下标大于左边i或者k的值，这是"无后效性"的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。
在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。对状态和“最优子结构”的关系的进一步解释，什么是动态规划？动态规划的意义是什么？ - 王勐的回答 写的很好，大家可以去读一下。

需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，存在一个有后效性的定义，不代表该问题不适用动态规划。这也是其他几个答案中出现的逻辑误区：
动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。

有位答主说：
分治在求解每个子问题的时候，都要进行一遍计算
动态规划则存储了子问题的结果，查表时间为常数这就像说多加辣椒的菜就叫川菜，多加酱油的菜就叫鲁菜一样，是存在误解的。

文艺的说，动态规划是寻找一种对问题的观察角度，让问题能够以递推（或者说分治）的方式去解决。寻找看问题的角度，才是动态规划中最耀眼的宝石！（大雾）

3. 什么是动态规划？动态规划的意义是什么

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
举例：
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

4. 如何理解动态规划

动态规划中递推式的求解方法不是动态规划的本质。  我曾经作为省队成员参加过NOI，保送之后也给学校参加NOIP的同学多次讲过动态规划，我试着讲一下我理解的动态规划，争取深入浅出。希望你看了我的答案，能够喜欢上动态规划。  0. 动态规划的本质，是对问题状态的定义和状态转移方程的定义。 引自维基百科 dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。 本题下的其他答案，大多都是在说递推的求解方法，但如何拆分问题，才是动态规划的核心。 而拆分问题，靠的就是状态的定义和状态转移方程的定义。  1. 什么是状态的定义？  首先想说大家千万不要被下面的数学式吓到，这里只涉及到了函数相关的知识。 我们先来看一个动态规划的教学必备题： 给定一个数列，长度为N， 求这个数列的最长上升（递增）子数列（LIS）的长度. 以 1 7 2 8 3 4 为例。 这个数列的最长递增子数列是 1 2 3 4，长度为4； 次长的长度为3， 包括 1 7 8; 1 2 3 等.要解决这个问题，我们首先要定义这个问题和这个问题的子问题。 有人可能会问了，题目都已经在这了，我们还需定义这个问题吗？需要，原因就是这个问题在字面上看，找不出子问题，而没有子问题，这个题目就没办法解决。  所以我们来重新定义这个问题： 给定一个数列，长度为N， 设为：以数列中第k项结尾的最长递增子序列的长度. 求 中的最大值.显然，这个新问题与原问题等价。 而对于来讲，都是的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第中某项结尾的LIS。  上述的新问题也可以叫做状态，定义中的“为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。 之所以把做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。   对状态的定义只有一种吗？当然不是。 我们甚至可以二维的，以完全不同的视角定义这个问题： 给定一个数列，长度为N， 设为： 在前i项中的，长度为k的最长递增子序列中，最后一位的最小值. . 若在前i项中，不存在长度为k的最长递增子序列，则为正无穷. 求最大的x，使得不为正无穷。这个新定义与原问题的等价性也不难证明，请读者体会一下。 上述的就是状态，定义中的“为：在前i项中，长度为k的最长递增子序列中，最后一位的最小值”就是对状态的定义。   2. 什么是状态转移方程？ 上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。  比如，对于LIS问题，我们的第一种定义： 设为：以数列中第k项结尾的最长递增子序列的长度.设A为题中数列，状态转移方程为：  （根据状态定义导出边界情况） 用文字解释一下是： 以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。  第二种定义： 设为：在数列前i项中，长度为k的递增子序列中，最后一位的最小值设A为题中数列，状态转移方程为： 若则 否则：（边界情况需要分类讨论较多，在此不列出，需要根据状态定义导出边界情况。） 大家套着定义读一下公式就可以了，应该不难理解，就是有点绕。  这里可以看出，这里的状态转移方程，就是定义了问题和子问题之间的关系。 可以看出，状态转移方程就是带有条件的递推式。  3. 动态规划迷思 本题下其他用户的回答跟动态规划都有或多或少的联系，我也讲一下与本答案的联系。  a. “缓存”，“重叠子问题”，“记忆化”： 这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。 上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，不是动态规划的核心。  b. “递归”： 递归是递推式求解的方法，连技巧都算不上。  c. "无后效性"，“最优子结构”： 上述的状态转移方程中，等式右边不会用到下标大于左边i或者k的值，这是"无后效性"的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。 在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。对状态和“最优子结构”的关系的进一步解释，什么是动态规划？动态规划的意义是什么？ - 王勐的回答 写的很好，大家可以去读一下。  需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，存在一个有后效性的定义，不代表该问题不适用动态规划。这也是其他几个答案中出现的逻辑误区： 动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。  有位答主说： 分治在求解每个子问题的时候，都要进行一遍计算 动态规划则存储了子问题的结果，查表时间为常数这就像说多加辣椒的菜就叫川菜，多加酱油的菜就叫鲁菜一样，是存在误解的。  文艺的说，动态规划是寻找一种对问题的观察角度，让问题能够以递推（或者说分治）的方式去解决。寻找看问题的角度，才是动态规划中最耀眼的宝石！

5. 不能用动态规划求解的问题是

不能用动态规划求解的问题是一类问题，可以归类到我们总结的几类问题里去，但是不存在动态规划要求的重叠子问题（比如经典的八皇后问题），那么这类问题就无法通过动态规划求解。
动态规划是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。

动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便 。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

6. 什么是动态规划？动态规划的意义是什么？

动态规划是用来求解最优化问题的一种方法。常规算法书上强调的是无后效性和最优子结构描述，这套理论是正确的，但是适用与否与你的状态表述有关。至于划分阶段什么的就有些扯淡了：动态规划不一定有所谓的阶段。其实质是状态空间的状态转移。下面的理解为我个人十年竞赛之总结。基本上在oi和acm中我没有因为动态规划而失手过。所有的决策类求最优解的问题都是在状态空间内找一个可以到达的最佳状态。搜索的方式是去遍历每一个点，而动态规划则是把状态空间变形，由此变成从初始到目标状态的最短路问题。依照这种描述：假若你的问题的结论包含若干决策，则可以认为从初始状态（边界条件）到解中间的决策流程是一个决策状态空间中的转移路线。前提是：你的状态描述可以完整且唯一地覆盖所有有效的状态空间中的点，且转移路线包含所有可能的路径。这个描述是包含动态规划两大条件的。所谓无后效性，指状态间的转移与如何到达某状态无关。如果有关，意味着你的状态描述不能完整而唯一地包括每一个状态。如果你发现一个状态转移有后效性，很简单，把会引起后效性的参数作为状态描述的一部分放进去将其区分开来就可以了；最优子结构说明转移路线包含了所有可能的路径，如果不具备最优子结构，意味着有部分情况没有在转移中充分体现，增加转移的描述就可以了。最终所有的搜索问题都可以描述成状态空间内的状态转移方程，只是有可能状态数量是指数阶的，有可能不满足计算要求罢了。这样的描述下，所有的动态规划问题都可以转变为状态空间内大量可行状态点和有效转移构成的图的从初始状态到最终状态的最短路问题。于是乎，对于动态规划，他的本质就是图论中的最短路；阶段可以去除，因为不一定有明确的阶段划分。

7. 什么是动态规划？动态规划的意义是什么？

动态编程的本质不是递归或递归，也不需要在内存中纠缠时间。理解动态规划不需要数学公式进行干预，而是对所需空间长度的全面解释…首先需要了解哪些问题不是动态规划，才能解决理解动态规划上帝的必要性。
然而，我们可以理解递归贪婪搜索和动态规则之间的关系，并帮助那些总是使用动态规则作为解决方案来建立动态规则的人。当然，当你熟悉这个问题时，你可以直接得到这个想法。如果你需要它，加上它。动态规划是解决某类问题的方法！重点是如何识别“某种类型的问题”是一个动态的编程，它可以解决，而不是一个纠缠不清的解决方案，无论是递归或递归！如何识别DP能够解决的一类问题，需要讨论计算机的工作原理。计算机是一个状态机的本质，所有的数据存储在当前状态的内存，CPU只能使用当前状态计算出下一个状态（外部硬盘存储，甚至不认为他们只是扩大的状态，存储容量和不可改变的下一个状态的唯一的计算规则的当前状态）当你试图使用计算机来解决一个问题，实际上是在思考如何表达状态（这是存储在什么样的数据）和状态转移（如何计算一些变量和其他变量）。

所以所谓的空间复杂度是为了支持需要存储的最大状态数，所以所谓的时间复杂度是从初始状态到最终状态需要多少个步骤。它太抽象了，例如：我想计算第一百个非实例数，每个非状态数的例子都是问题，每一个都是一个新的第二个状态。因此，在同一时间，我们只需要节省两个国家在同一时间内。空间复杂度是常数。每次计算时，新的状态也是不变的，状态是线性增加的，所以时间复杂度也是线性的。上面的状态计算非常直接。它只需要根据固定模式从旧状态计算新状态。（一个[我] = [·] + [一]，I-2）不需要考虑更多的状态是必要的，也不需要选择哪个老状态来计算新的状态。对于这样的解决方案，我们称之为递归。在例子不太简单的情况下，使人们忽略了概念的阶段性，把阶段定义为问题的解决，同时获得不同状态的集合。非示例级数，每一步都会计算出一个新数，所以每个阶段只有一个状态。想象另一个问题。如果你在围棋棋盘上放置某个点，你只能一步一步走，因为你可以在东南和西北行走，所以当你走同一个四步时，你可能处于许多不同的位置。开头几步就是前几个阶段。在n的步骤中可能发生的位置称为状态。所有可能的位置的设置，现在的问题是，在舞台上，计算新的国家可能会遇到各种奇妙的情况，根据不同的情况，我们需要不同的方法，以下几点需要注意：如果有N个阶段，每个阶段有多个国家，在不同时期的状态数不需要同一个国家，一个阶段可以在几个国家得到的下一个阶段。然后，我们必须计算出最后阶段的状态数在经过之前自然地经过每个阶段的某些状态。好消息是，有时我们不需要真正计算所有的状态，比如这样一个智障的棋盘问题：从左上角到右下角，我们需要几个步骤。答案显然是，使用这种机智的问题是帮助我们了解阶段和状态。

的确，在某一阶段有多个状态，正如N步可以在这个问题上的许多位置一样。但是在同一个步骤中，在步骤1中，让我们走得最远的位置是什么？是的，它是在步骤n中最远的地方。一个熟悉的词被称为“最好的下一步是从当前最好的得到的”。因此，为了计算最终的最优值，它只需要存储每一步的最佳值，并且贪婪地解决与问题相符的问题。如果你看计算过程不是最佳状态之间的计算和非序列的例子呢？所以计算的方法是递归的。因为所有问题都可以分为阶段和状态。

这样，我们一次就解决了一大类问题：一个阶段中最好的一个阶段可以从上一阶段的最佳阶段获得。

8. 什么是动态规划？动态规划的意义是什么

动态规划中递推式的求解方法不是动态规划的本质。0. 动态规划的本质，是对问题状态的定义和状态转移方程的定义。
动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
本题下的其他答案，大多都是在说递推的求解方法，但如何拆分问题，才是动态规划的核心。
而拆分问题，靠的就是状态的定义和状态转移方程的定义？