细讲动态规划坐标型_动态规划 交叉点

什么是动态规划

动态规划（Dynamic Programming 简称DP）是解决“多阶段决策问题”的一种高效算法。

通过合理组合子问题的解从而解决整个问题解。其中的子问题并不是独立的，这些子问题又包含有公共的子子问题。

…… 动态规划算法就是对每个子问题只求一次，并将其结果保存在一张表中(数组)，以后再用到时直接从表中拿过来使用，避免重复计算相同的子问题。

“不做无用功”的求解模式，大大提高了程序的效率。 常用于解决统计类问题（统计方案总数）和最优值问题（最大值或最小值）。

动态规划的基本模型

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。如下图所示：

 多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。

最优化原理与无后效性 

上面已经介绍了动态规划模型的基本组成，现在需要解决的问题是：什么样的“多阶段决策问题”才可以采用动态规划的方法求解。            

一般来说，能够采用动态规划方法求解的问题，必须满足最优化原理和无后效性原则：            1. 动态规划的最优化原理。作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，而非最优解对问题的求解没有影响。在例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径，也必然是该点到终点E的一条最优路径，即整体优化可以分解为若干个局部优化。            

2. 动态规划的无后效性原则。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。在例题1最短路径问题中，问题被划分成各个阶段之后，阶段K中的状态只能由阶段K+1中的状态通过状态转移方程得来，与其它状态没有关系，特别与未发生的状态没有关系，例如从Ci到E的最短路径，只与Ci的位置有关，它是由Di中的状态通过状态转移方程得来，与E状态，特别是A到Ci的路径选择无关，这就是无后效性。            

由此可见，对于不能划分阶段的问题，不能运用动态规划来解；对于能划分阶段，但不符合最优化原理的，也不能用动态规划来解；既能划分阶段，又符合最优化原理的，但不具备无后效性原则，还是不能用动态规划来解；误用动态规划程序设计方法求解会导致错误的结果。

动态规划问题解题步骤

1.根据时间或空间确定要去的状态

2.写出动态规划方程

3.求解：记忆化搜索；递推（倒推或者正推）

一、坐标型

在二维坐标系内，规定了方向，求最优值问题

比较容易根据方向写出动态规划方程

一般方程也是二维的f[i][j]

例：公共汽车

【问题描述】 一个城市的道路，南北向的路有n条，并由西向东从1标记到n,东西向的路有m条，并从南向北从1标记到m,每一个交叉点代表一个路口，有的路口有正在等车的乘客。

一辆公共汽车将从(1,1)点驶到（n,m）点，车只能向东或者向北开。

问：司机怎么走能接到最多的乘客。

 【输入】  第一行是n,m,和k,其中k是有乘客的路口的个数。以下k 行是有乘客的路口的坐标和乘客的数量。已知每个路口的乘客数量不超过1000000。

n,m<=1000

【输出】  接到的最多的乘客数

a[i,j] ：

(i,j)位置的人数 f[i,j]：

从(1,1)走到(i，j)能接的最多人数 f[i,j]=max{f[i-1,j],f[i,j-1]}+a[i,j]