文档介绍：SWUST ACM系列讲座之动态规划 (dynamic programming)
信息学院ACM集训队
主讲人：Flying-马飞
动态规划 SWUST ACM系列讲座之动态规划 (dynamic programming)
信息学院ACM集训队
主讲人：Flying-马飞
动态规划 (dynamic programming)
实际上，动态规划的实质就是通过保存计算过的状态，来避免递归的重叠子问题．解决冗余，是动态规划的根本目的．
动态规划实质上是一种以空间换时间的技术,我们舍空间而取时间。
动态规划的适用条件
１．最优化原理（最优子结构性质） 最优化原理可以这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
动态规划的适用条件
２．无后向性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
状态和状态转移
状态的选择和状态转移方程是解决动态规划的关键所在．
动态规划的实现
动态规划一般有以下两种实现方法：
：当需要求一个状态时，首先看这个状态是否被计算过，如果计算过，直接使用计算过的值；否则，计算一次，并保存结果．一般用递归实现．
：所谓递推就是，按照一定顺序将一定范围内的所有状态都计算出来．一般用非递归的形式实现．
典型问题:0-1背包问题
题目叙述：
给定n种物品和一个背包,物品i的重量是wi,价值为vi背包容量为C .如何选择物品使背包中的总价值最大?
背包问题可以看作是决策一个序列(x1,x2…xn),对任何变量Xi的决策是Xi=1或Xi=-1决策后,已确定了(x1,x2…xi-1),在决策Xi时,问题处于下面两个状态之一:
,则Xi=0,背包价值不变;
,则Xi=1,背包价值增加Vi.
两种情况下背包价值最大者应该是对Xi决策后的背包价值.
令v(i,j)表示在前i(1<=i<=n)个物品中能装入容量为j(1<=j<=C)的背包的物品的最大值,可以得到如下动态规划函数:
V(i,0)=V(0,j)=0;
V(i-1,j) j<wi
V(i,j)=
max{V(i-1,j),V(i-1,j-wi)+vi} j>wi
上面就是0-1背包问题的状态转移方程,这也是动态规划中最难,最重要的,只有找到好的状态和它的转移方程才能用动态规划解决好问题.
典型
三角形
给定一个具有N层的数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，计算从顶部至底部某处一条路径，使得该路径所经过的数字总和最大。
2
6 2
1 8 4
1 5 6 8
用二元组dp(i,j)描述问题，dp(i,j)表示从顶层到达第i层第j个位置的最大路径。
显然到达i点的路径只能来自于上一层的j-1点或者j点，所以：
dp(i,j)=max{dp(i-1,j),dp(i-1,j-1)}+a(i,j) dp(1,1)＝a(1,1)
我们需要的最终需要的解就是:
max{dp(N,k)} 1<= k <= N 。
问题解决！
代码 :
ans=0;         for(i=1;i<=n;i++)             for(j=1;j<=i;j++)             {                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];                 if(i==n)
                {                     if(dp[i][j]>ans)                     {                         ans=dp[i][j];                     }                 }             }