坐标规则类动态规划,,数塔问题,给定一个数塔，如下所示在此数塔中，从顶部出发，在每一节点可以选择向左走还是向右走，一直走到底层请找出一条路径，使路径上的数值和最大59） 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16,数塔问题,贪心可行？不行！搜索可行？可行，但费时！动态规划自底向上逐层分阶段决策第1次决策，针对第4层如果最优路径经过2，则从第4层到第5层应该经过19，则第4+第5层的最大路径为2+19=21如果最优路径经过18，则从第4层到第5层应该经过10，则第4+第5层的最大路径为18+10=28……这样实际上将5阶数塔变为4阶数塔问题了逐层向上递推，最后得到问题的最优解,动态规划算法思想总结,每个阶段都使问题规模变小，更接近最优解。
子问题与原问题类型相同子问题的最优解是原问题最优解的一部分直到最后一步，问题的规模变为1（自底向上的过程），就找到了问题的最优解可以将DP特点归纳为：全面分阶段地解决问题，或者带决策的多阶段多方位的递推算法数塔问题实现,存储数塔数据结构data[i,j]程序流程图及代码实现d[i,j]=data[i,j] i=n(最下层)d[i,j]=max(d[i+1,j],d[i+1,j+1])+data[i,j] i=1..n-1,j=1..n,动态规划算法的一般解题思路（1）,通过数塔问题我们可以看到DP的一般解题思路分阶段就是问题求解过程的不同阶段或问题的规模，所以我们要知道该问题是要：求什么？如果分阶段的话，从一个阶段到另一个阶段是什么在变化？即状态，也就是最优解的形式在每个状态综合考虑考虑在这个阶段的所有状态变化怎么变化的呢？需要列出状态变化的方程，可以方便计算即不同阶段的递推关系，也即不同规模的问题与子问题的递推关系根据递推关系计算自上而下的递归/自下而上的递推填表,动态规划算法的一般解题思路（2）,找出最优解的性质，并刻划其结构特征递归地定义最优值以自底向上的方式计算出最优值根据计算最优值时得到的信息，构造最优解。
Robots,在一个n*m的棋盘内，一些格子里有垃圾要拾捡现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走每次他到达一个点，就会自动把这个点内的垃圾拾掉问：最多能拾多少垃圾在最多的情况下，有多少种拾垃圾方案？数据范围:n<=100,m<=100,样例分析,最多能拾5块有4种方法分析(1),因为机器人只能向右或者向下走符合无后效性原则于是考虑动态规划设F(i,j)表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾F(i,j)=Max{f(i-1,j),f(i,j-1)}+c[i,j]其中C[i,j]=1表示(i,j)点有垃圾C[i,j]=0表示没有1<=i<=n,1<=j<=m，决策2种时间复杂度为O(n*m),分析(2),设G[i,j]表示在f[i,j]最大的时候，有多少种方案捡到f(i,j)的垃圾只能从两个方向来走，方案数累加即可因此， g(i,j)=g[i-1,j]*k+g[i,j-1]*L 如果f[i-1,j]+c[i,j]=f[i,j]，则K=1否则K=0 如果f[i,j-1]+c[i,j]=f[i,j]，则L=1否则L=0时间复杂度O(n*m),矩阵取数游戏 （NOIP2007）,对于一个给定的n*m的矩阵，矩阵中的每个元素aij为非负整数。
游戏规则如下：1. 每次取数时须从每行各取走一个元素，共n个 m次后取完矩阵所有的元素；2. 每次取走的各个元素只能是该元素所在行的行首或行尾；3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；4. 游戏结束总得分为m次取数得分之和求出取数后的最大得分样例,输入 2 3 1 2 4 3 4 2输出 82第1次：第一行取行首元素，第二行取行尾元素，本次的氛围1*21+2*21=6第2次：两行均取行首元素，本次得分为2*22+3*22=20第3次：得分为3*23+4*23=56总得分为6+20+56=82,数据范围,60%的数据满足：1<=n, m<=30，答案不超过1016100%的数据满足：1<=n, m<=80，0<=aij<=1000,分析,首先，n行求值可以独立考虑！设f[i,j]表示区间i-j的最优值f[i,j]=max{f[i+1,j]+w*a[i] , f[i,j-1]+w*a[j]}其中w=w+w,即w*2需要做若干次高精度加法和乘法直到求出，max{f[i,i]+w*a[i]，i=1..m}为止。
传纸条(NOIP2008),小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递班里每个同学都可以帮他们传递，但只会帮他们一次每个同学愿意帮忙的好感度有高有低，可以用一个0-100的自然数来表示，数越大表示越好心小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大现在，请你帮助小渊和小轩找到这样的两条路径1<=m,n<=50,贪心,很容易想到一个算法：求出1个纸条从（1，1）到（M,N）的路线最大值.删除路径上的点值再求出1个纸条从（M,N） 到（1，1）的路线最大值.统计两次和上述算法很容易找出反例，如下图第1次找最优值传递后，导致第2次无法传递分析,贪心算法错误，因此我们需要同时考虑两个纸条的传递由于小渊和小轩的路径可逆，因此，尽管出发点不同，但都可以看成同时从(1,1)出发到达(M,N)点设f(i1,j1,i2,j2)表示纸条1到达(i1,j1)位置，纸条2到达(i2,j2)位置的最优值则有，其中 (i1,j1) (i2,j2)1<=i1, i2<=M, 1<=j1 , j2<=N时间复杂度O(N2M2),分析2,另一种思路：每个纸条都需要走M+N步才能达到目标。
因此，设F(k,i1,i2)表示两个纸条都走了K步，第1个纸条横坐标为i1,第2个纸条横坐标为i2的最优值则两个纸条的纵坐标分别为j1=K-i1, j2=K-i2 ,状态转移方程如下：其中 i1i21<=i1, i2<=M,1<=k<=N+M时间复杂度O((N+M)*M2),。