动态规划步骤
动态规划的性质？
动态规划的性质？
局部最优才能保证全局最优.
动态规划的定义中就提到,动态规划的问题必须满足最优子结构的性质和无后效性的性质.
子问题的重叠性则能省去很多重复的步骤,可以高效的利用动态规划的两种实现方式：
记忆化以及递推.其中递推又可以用顺推和倒推两种实现方式.
如何写动态规划状态转移方程？
使用动态程序设计方法解题的步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
划分阶段：
按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
选择状态：
将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：
之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
写出规划方程（包括边界条件）：
动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。
这是我的资料，你先看看，动态规划什么无后效性的理论我也不是太明白，不过大意就是按你划分的阶段看，当前阶段的选择不影响后面的阶段。
不明白也没关系，多做几道题，过一段就自然而然的知道了。
学习DP当然要有简单到困难啦，我先看的是数字三角形这一类的，然后学的背包九讲，你也可以试试。
数字三角形问题
下图示出了一个数字三角形。数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。
38
810
2774
45265
假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，文件sum.out输出最大值。
输人数据：由文件sum.in输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。
分析：
如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该问题是一个典型的多阶段决策最优化的问题。算法设计与分析如下：
采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段……第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。我们在实现程序的时候可以这样设计：
假设用a[i，j]表示三角形第i行的第j个数字，用p[i，j]表示从最顶层到a[i,j]这个数字的最佳路径(路径经过的数字总和最大)的数字和，易得问题的动态转移方程为：
p[0,0]=0
p[i,j]=max{p[i-1,j] a[i,j],p[i-1,j-1] a[i,j]}
(1≤j≤i≤n，其中n为总行数),则max{p[n,j]}1≤j≤n为问题解。
或者
采用动态规划中的逆推解法。
假设用a[i，j]表示三角形第i行的第j个数字，用p[i，j]表示从最底层到a[i,j]这个数字的最佳路径(路径经过的数字总和最大)的数字和，易得问题的动态转移方程为：
p[n 1,j]=0(1≤j≤n 1)
p[i,j]=max{p[i 1,j] a[i,j],p[i 1,j 1] a[i,j]}
(1≤j≤i≤n，其中n为总行数),p[1,1]为问题的解。