动态规划

1. 动态规划

 动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解 决策过程最优化 的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
   虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如 线性规划、非线性规划 )，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
   在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定， 它依赖于当前面临的状态，又影响以后的发展 。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个 前后关联具有链状结构的多阶段过程 就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的， 决策依赖于当前状态，又随即引起状态的转移 ，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法
   动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。 动态规划算法与分治法类似 ，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是， 适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的 。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
   以一个例子来说明动态规划的概念(leetcode第5题最长回文子串)：
   在这个例子中，一个字符串如果是回文子串，那么去掉头尾也照样是回文子串。而每一个字符都有可能是最长回文子串的一部分。
   上面这个例子使用一个二维数组表示各个阶段的状态，这个二维数组的行是子串的起始位置，列是子串的结束位置。由于j>=i，所以只需要考虑二维数组的主对角线的上半部分，对角线上的值永远是true。用true表示这个子串是回文串，false不是回文串。那么对于某个固定位置的数组元素来说，它的值依赖于左下角的元素的值。进行填充的时候只能一列一列地进行填充，同一列的元素从上到下依次填充。

2. 动态规划

 与贪心算法求局部最优解相比，动态规划求的是全局最优解（但不是每个问题都有最优解，比如NP完全问题就没有最优解）
    例： 背包问题之动态规划解决   问题描述：   现在有一个背包可以装4磅物品，现在要从商城里拿尽可能价值高的物品装进包里。   商城物品情况如下
    每个动态规划都从一个网格（如下）开始    现在一行一行地填充该网格。
   每个格子的计算公式：
                                           填充吉他行 目前最大价值1500（吉他）
   填充音箱：目前最大价值3000（音箱）
   填充笔记本：目前最大价值3500（吉他+笔记本）
   动态规划的原则就是将大问题拆解成多个小问题，先把小问题的最优解求出，再在考虑小问题最优解的前提下，得出最终问题的最优解   本例的背包问题中，先求出只有吉他一种物品时的最优解，再逐步添加物品，最终求出最优解
                                           关于网格计算公式的补充：   整个动态规划求解过程中，是从小问题层逐步求解到大问题，自然每个格子要考虑的第一点就是前一格子的最大值，又，新的一层添加了新物品，所有也要考虑新物品的价值+剩余可用磅数的最大价值（上一层求得）
   背包问题补充：    若再添加一个物品 ——项链{‘价值’：1000$，‘重量’：0.5磅}   此时如果沿用之前的网格   
                                           
    如果要装的物品为燕麦，木豆，大米 这种可以一部分一部分取出的物品   动态规划则解决不了这种情形，贪心可以。
    旅游行程问题 
   当然我们可以用动态规划的网格法来得到一条最有价值的旅游路线
   如果加入以下景点
   在去巴黎的景点所花费的时间中，有0.5天是从伦敦前往巴黎的时间。   因此如果先去了埃菲尔铁塔,则去巴黎的剩下两个景点的花费时间也要减少2个小时
   这种情况就不能使用之前的动态规划算法。
    动态算法处理的每个子问题都是离散的 
   再来看一个案例   假如你要经营一个网站，网站主要任务是：英文单词翻译。即用户输入英文单词，你给出相应的翻译。  例用户输入fish，网站输出鱼   如果用户输入的hish，但词典中并没有该单词，此时应给出相似词。   怎么样才算是相似词呢？判断最大子串长度？    利用动态规划求出两字符串（fish和hish）的最大字串长度    动态规划解决问题总是要先知道网格中的各个元素：   两个坐标轴是什么？网格中的值是什么（通常为要 优化的指标 ）   1，分解问题：要求fish和hish的最大子串，可以先求其字串的最大公共子串（如先求fis和his）。考虑两个坐标轴为两个单词，则网格中的值为最大子串的长度。
   接下来填充该网格。不断验证得到单元格公式：
                                           单元格公式解释：   1）两字母相同，则局部最大字串要延长，即斜上方（cell[i][j]）的值加一(这里指标值在斜方向上累加)   2）若是不同，则局部最大字串为0
   两字符串的最大字串长度即为网格中的最大值3。
    如果用户输入fosh，那么要返回fish还是fort呢？    如果判断依据为最大子串，则会返回fort，但实际上fish和fosh更像！   因此我们考虑判断依据为两字符串的最大公共子序列长度（即两字符串公共字符的个数）   求最大公共子序列的单元格公式为：   
                                           
   fosh和fort的最大公共子序列长度为2
   fosh和fish的最大公共子序列长度为3   此时就可以返回正确结果fish而非fort。
   1，动态规划通常用于解决 在给定约束条件下优化某个指标值    2，动态规划的原则就是：将大问题分解成小问题，在解决了小问题的条件下，逐步求解大问题。（一个分解问题的方法就是，将条件逐渐减少，从最简单的情况开始分析）   3，动态规划使用的一个必要条件为： 分解出来的每个小问题都是离散的    4，每种动态规划方案都设计网格   4.1，网格的每个格子都是一个小问题   4.2，网格的每个格子的值都是指标的值   4.3，单元格计算公式需要 具体问题具体分析 。

3. 动态规划之解题思路

一、定义
  
 动态规划（dynamic programming)简称DP，用于解决重叠子问题。
  
 二、解题步骤
  
 1、确定dp数组以及下标含义
  
 2、确定状态转移方程
  
 3、dp数组的初始化
  
 题目有两种可能，一种是要求背包恰好装满，一种是可以不装满（只要不超过容量就行）。
  
 - 恰好装满。只需要初始化dp[0] 为 0， 其他初始化为负数即可。
  
 - 可以不装满。 只需要全部初始化为 0，即可。
  
 4、确定遍历的顺序
  
 外层遍历物品，还是外层遍历容量；
  
 以及容量从大到小遍历，还是从小到大遍历。
  
 5、举例检验
  
 三、总结
  
 递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。
  
 动态规划内容很多，将从以下方面进行学习：
  
 斐波拉契数列
  
 背包（0-1背包，完全背包）。。。。。
  
 参考资料： github分类详解

4. 动态规划问题求解步骤

动态规划求解步骤：

a. 找出最优解的性质，并刻划其结构特征。b. 递归地定义最优值。c. 以自底向上的方式计算出最优值。d. 根据计算最优值时得到的信息，构造最优解

动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E. Bellman等人提出的，应用于工程领域。动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

5. 动态规划的基本概念

1.阶段
阶段是指研究的事物在发展过程中所处的时段或地段。处理多阶段决策问题，需要将全过程划分若干阶段，每个阶段进行一次抉择。若演变过程是离散的，则用序列编号i=1，2，…，n表示，称为阶段变量。它可以是空间，也可以是时间。若为时间，则按相等增量Δt离散，或按连续变化，以变量t表示。
2.状态
在多阶段决策过程中，各阶段演变可能发生的情况，称为状态。描述状态的变量称为状态变量。一个阶段可能有若干个状态。若第i阶段有m个状态变量，可用si表示该阶段的状态集合：

华北煤田排水供水环保结合优化管理

3.决策
决策是某阶段状态给定之后，从该状态演变到下一阶段某状态的选择。当阶段的初始状态给定后，做出某一决策，则本阶段的初始状态就变成该阶段的末状态，做出不同的决策，就得出不同的末状态。描述决策变化的量，称为决策变量。常用di（si）表示第i阶段状态处于si时的决策。在实际问题中，决策变量的取值往往被限制在某一范围之内，此范围称为允许决策集合或决策空间，常用di（si）∈Di（si）表示。
4.策略
策略是指一个决策序列。由第1阶段开始至终点为止的过程，称为问题的全过程；由每个阶段的决策di（si）（i=1，2，…，n）所组成的决策序列，称为全过程策略，简称策略，记为P1n。
则

华北煤田排水供水环保结合优化管理

从k阶段开始至终点的过程，称为原问题的后子过程（或称k子过程），其决策序列称为k子过程策略，简称子策略，即

华北煤田排水供水环保结合优化管理

在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合，以P表示。从允许策略范围集合中，找出达到最优效果的策略，称为最优策略，最优策略相应的状态序列，称为最优轨迹。
5.状态转移方程
下一阶段状态Sk+1是本阶段状态变量Sk和决策变量Xk（Sk）的函数，即对于状态Sk的决策结果是Sk+1，记为

华北煤田排水供水环保结合优化管理

简写为

华北煤田排水供水环保结合优化管理

这种从某状态出发到下一阶段某状态的转移规律称为状态转移方程。
6.目标函数
在多阶段最优决策过程中，目标函数是用来衡量策略优劣的数量指标。
状态的转移就产生费用（效益）的改变，它们是同时发生的。设ri表示i阶段的费用（效益），则ri也是si及di的函数，可写为

华北煤田排水供水环保结合优化管理

此式称为第i阶段的费用（效益）方程。若从过程的第一阶段初始状态开始，经历全部阶段，可得到全过程的总费用R，即总费用R是各阶段费用ri的总和，表示为

华北煤田排水供水环保结合优化管理

因为状态和决策往往是一个向量，所以总费用R也是一个向量，其最优值的数量指标，就是过程的目标函数，常用R*表示，即

华北煤田排水供水环保结合优化管理

式中：Opt（optimization）表示最优值，可取极大或极小，依目标性质而定。
通过以上讨论，可将多阶段决策过程归纳为如图3-1所示。

图3-1 多阶段决策过程示意图

6. 什么是动态规划？

动态规划算法   概念及意义　　动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
　　动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
　　虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 
　　动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。  基本模型 　　
　　多阶段决策过程的最优化问题。
　　在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 
　　这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。  记忆化搜索 　　给你一个数字三角形, 形式如下:
　　1
　　2 3
　　4 5 6
　　7 8 9 10
　　找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.
　　无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}
　　对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。
　　解决方法：
　　我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程 :
　　f1:=f(i-1,j+1); f2:=f(i-1,j);
　　if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];
　　显而易见，这个算法就是最简单的搜索算法。时间复杂度为2^n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的. 状态 决策 　　
　　决策：
　　当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。
　　状态：
　　我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态确定后,以前状态就已经确定,则无需枚举.
　　  动态规划算法的应用 　　一、动态规划的概念
　　近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。
　　要了解动态规划的概念，首先要知道什么是多阶段决策问题。
　　1. 多阶段决策问题
　　如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。
　　各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.
　　2．动态规划问题中的术语
　　阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。
　　在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。
　　状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。
　　在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。
　　过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。
　　当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。
　　无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
　　决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多间题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。
　　决策变量的范围称为允许决策集合。
　　策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。
　　给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。
　　最优性原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。
　　最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到D，我们知道，最短路径是A�8�1B1�8�1C2�8�1D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：A�8�1B1�8�1C2是A到C2的最短路径，B1�8�1C2�8�1D也是B1到D的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。

7. 动态规划是什么

　是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱.
　　动态规划首次进入信息学奥赛是在IOI94（数字三角形），在国内首次出现是在NOI95。此后动态规划成为信息学奥赛的必考算法之一。
[编辑本段]概念及意义
　　动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
　　动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
　　虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 
　　动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。
[编辑本段]基本模型
　　
　　多阶段决策过程的最优化问题。
　　在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 
　　这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。
[编辑本段]记忆化搜索
　　给你一个数字三角形, 形式如下:
　　1
　　2 3
　　4 5 6
　　7 8 9 10
　　找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.
　　无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}
　　对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。

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

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