动态规划

简介

动态规划最短路径示意图

动态规划（Dynamic Programic）最早是运筹学的一个分支，是求解多阶段决策问题的一类方法。

多阶段决策问题值得是一类问题可以分解为若干个相互联系的阶段，每个阶段做出的决策不仅影响当前阶段，还会影响下一阶段的状态。反之，也可以理解为每个阶段决策的过程需要依赖前序阶段的结果。

在多阶段决策问题中，每个阶段决策结果确定构成了决策序列，多阶段决策问题就是使得决策序列中的策略总的收益最优。

动态规划用来解决多阶段决策过程中最优方案等问题的方法，其特点是将多位决策问题转换为几个一维的问题分别去解决。

动态规划中的基本概念有阶段，状态等，决策，策略，状态转移方程等。


概念	名词解释
阶段	把求解问题的过程分解成若干个相互联系的阶段，每个阶段可以独立的按照次序进行求解。
状态	每个阶段所处的各种客观条件，通常一个阶段有若干状态，描述这些状态的变量成为状态变量。
决策	动态规划过程中求解某一个阶段的状态时，可以作出的不同决定称为决策，决策会影响下一阶段的状态。
策略	按次顺排序的决策组成的集合称为策略。
状态转移方程	描述状态之间变迁的过程，确定状态转移规律。

动态规划解决的问题一般有下列特点：


特点	解释
重叠子问题	相同的子问题可以被重复求解。
最优子结构	问题的最优解可以由子问题的最优解推倒出来。
无后效行	当前阶段可以独立求解，过程不受到之前状态的影响。例如迷宫问题中不能走之前重复的路，这就是有后效行的一个典型场景。

动态规划一般分为确定变量，确定状态转移方程，确定边界条件等三个步骤。

确定状态和状态变量
- 分析问题特点，按照时间或者空间特征，将问题分为有序的若干阶段，因为动态规划是按顺序递推求解，所以阶段一定是可排序的。
- 确定问题每个阶段求解时的状态，确定所需要的变量。求解过程一般是确定dp数组以及下标的含义。

确定状态转移方程
- 分析决策过程，确定状态转移方程，决策和状态转移是相互联系的，状态是根据上一阶段状态以及当前决策变迁到当前状态的，所以确定决策就可以明确状态迁移方程，实际求解过程中，往往根据当前阶段和上一阶段的状态差异，推导决策过程。
确定边界条件
- 状态转移方程是递推的过程，所以需要确定递推的边界条件。因为递推过程是从前到后依次执行的，所以边界条件一般就是初始值。

假如你在爬一个N层台阶的楼梯，每次可以爬一个或者2个的台阶，你有多少种不同的方式可以爬上楼梯呢？

确定状态变量，爬N层台阶，可以按照所在台阶的位置划分阶段。假设爬上第N层台阶的方式是f(n)。
确定状态转移方程，动态规划往往从后往前推到决策过程，如果当前状态位于第N级台阶，那么根据状态变量，到达当前台阶，要么走1步，要么走2步，也就是其上一个阶段是f(n-1)或者f(n-2)。所以可以确定状态转移方程是f(n) = f(n-1)+f(n-2)。
确定边界条件，因为状态转移方程中有前两个阶段有关，所以边界需要有两个值。显而易见的是f(1)=1，f(2)=2（可以1个2步或者2个1步）。

爬楼梯问题的状态表达式如下：

$f(n)={\begin{cases}f(n-1)+f(n-2),n>2\\2,n=2\\1,n=1\end{cases}}$

实现代码如下：

一个棋盘有n行m列，从棋盘的左上角走到右下角，每次只能往右走一步，或者往下走一步，总共有多少种走法？

确定状态变量，和爬楼梯问题一样，依然把棋盘上的每个位置作为一个阶段。因为棋盘是二维的，所以状态变量是两个，横坐标和纵坐标分别是i，j的位置，假如当前位置的走法是f(i, j)。
确定状态转移方程，当前阶段的上一个阶段相差往右一步或者往下一步，所以状态转移方程是f(i, j) = f(i-1, j) + f(i, j-1)。
确定边界条件，因为方程中有两个变量，而且有i-1和j-1，所以处于稳妥考虑，将f(0, 0)，f(0, 1)， f(1, 0)作为边界。

$f(i,j)={\begin{cases}f(i-1,j)+f(i,j-1),i>1,j>1\\1,i=1,j=0\\1,i=0,j=1\\0,i=0,j=0\end{cases}}$

实现代码如下：

一个棋盘有n行m列，从棋盘的左上角走到右下角，每次只能往右走一步，或者往下走一步，并且其中有一些障碍点无法经过，总共有多少种走法？

确定状态变量，和简单走棋盘类似，假如当前位置的走法是f(i, j)。
确定状态转移方程，当前阶段的上一个阶段相差往右一步或者往下一步，所以状态转移方程是f(i, j) = f(i-1, j) + f(i, j-1)，但是如果是障碍点的话，因为没有路径可以到达障碍点，所以坐标m，n如果是障碍点，则f(m, n) = 0。
确定边界条件，因为方程中有两个变量，而且有i-1和j-1，所以处于稳妥考虑，将f(0, 0)，f(0, 1)， f(1, 0)作为边界。
$f(i,j)={\begin{cases}f(i-1,j)+f(i,j-1),i>1,j>1\\1,i=1,j=0\\1,i=0,j=1\\0,i=0,j=0,(i,j)=(m,n)\end{cases}}$

一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？背包问题有很多变种，此处介绍的是01背包问题，也就是每件问题只能选1件或者不选。