思考：
数字三角形II：有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如下图所示。
数字三角形问题II
从第一行的数开始，除了某一次可以走到下一行的任意位置外，每次都只能左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走，使得这个和尽量大？
稍微修改一下以后，原来的解法不适用了，如果仍然记d[i,j]为以格子(i,j)为根的子三角形的解，那么第一步到底是可以任意移动，还是只能往左下或右下走一格呢？不一定，这取决于解决这个子问题之前做过什么事。
后效性：刚才的状态定义有后效性（无后效性有时也称子问题的独立性），即先前的决策可能影响后续的决策。解决方法是扩展状态定义，把有后效性的部分包含进来。记d[i][j][k]为以格子(i,j)为根的子三角形的解，k=1表示可以任意移动，k=0表示不能任意移动，则原来问题的解是d[1][1][1]。当k=1时可以任意移动，然后k=0，而k=0时不能任意移动。状态转移方程需要分类讨论，写成程序是：
if(i==n)d[i][j][k]=a[i][j];
else { d[i][j][k]=max(d[i+1][j][k],d[i+1][j+1][k]); // normal move
if(k==1) // teleport for (t=1;t<=i;i++)
if(d[i][j][k] } 当然，所有d[i][j][0]的最大值可以边计算边记录，像这样： memset (max,0,sizeof(max)); for (j=1;j<=n;j++) { d[n][j][1]=d[n][j][0]=a[n][j]; if(a[n][j]>max[n]) max[n]=a[n][j]); } for (i=n-1;i>=1;i--) { for(j=1;j<=i;j++) { d[i][j][0]=max(d[i+1][j][0],d[i+1][j+1][0]); // normal move if(d[i][j][0]>max[i]) max[i]=d[i][j][0]; // update max d[i][j][1]=max(d[i+1][j][1],d[i+1][j+1][1],max[i+1]); // normal move / teleport } } 免去了一次循环，时间复杂度仍为O(n2)。 数字三角形III：有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如下图所示。 数字三角形问题III 从第一行的数开始，每次都只能左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走，使得这个和的个位数尽量大？ 这次没有后效性了，但是又有了新的问题。 错误方程1：d[i][j]=max{d[i+1][j],d[i][j+1]}+a[i][j]。反例：如果d[i+1][j] =5，d[i][j+1]=6，a[i][j]=9，那么加起来是14或15，是两位数； 错误方程2：d[i][j]=(max{d[i+1][j], d[i][j+1]}+a[i][j]) mod 10。反例：d[i+][j]=6, d[i][j+1]=9，a[i][j]=2，虽然6比9小，但是6+2的个位数比9+2的个位数大。 错误方程3：d[i][j]=max{(d[i+1][j]+a[i][j])mod 10, (d[i+1][j+1]+a[i][j]) mod 10}。这个错误比较隐蔽，它并不是来源于方程本身的错误，而是状态定义的错误。 方程三错误示意图 数字三角形上的数如上图。对于灰色格子(2,1)来说，根据状态定义，d[2][1]=6（从此格子出发路径上数之和的最大个位数），d[2][2]=0（无论怎么走，个位数都是0），根据前面的“递推方程”算出d[1][1]应是1，但实际上d[1][1]等于9。事实上，对于相同的d[2][1]和d[1][1]可能会有不同的d[1][1]，所以不存在从d[2][1]和d[2][2]得到d[1][1]的递推公式！也就是说，并不能怪我们没有找到正确的状态转移方程，实在是因为这样的状态定义根本无法递推！ 问题出在哪里呢？关键是：全局最优解5-0-4-0并没有包含子问题最优解0-4-2。由于d值只保留“子问题最优解”，当全局最优解并没有包含子问题最优解时，d值无法递推。 【最优子结构】在贪心法介绍中曾经提到过最优子结构。这样的结构在动态规划中也是需要的。不满足最优子结构的情况通常也可以考虑扩展状态定义。在本例中，记d[i][j][k]表示以格子(i,j)为根的子三角形是否存在所有数之和个位为k的路径，则d[i][j][k]为真当且仅当存在t使得(a[i][j]+t) mod 10=k，且d[i+1][j][t]或d[i+1][j+1][t]为真。 memset (d,0,sizeof (d )); // false for (j=1;j<=n;j++) d[n][j][a[n][j]]=true ; for (i=n-1;i>=1;i--) for (j=1;j<=i;j++) for (k=0;k<=9;k++) { d[i][j][k]=false ; for(t=0;t<=9;t++) // lookup suitable t if ((a[i][j]+t )==k && (d[i+1][j][t]||d[i+1][j+1][t])) d[i][j][k]=true ; } 这个程序是对的，但稍稍有点别扭。如果a[i][j]=5和k=5，需要检查的只有t=0，不需要从0到9依次判断一次，即： for (i=n-1;i>=1;i--) for (j=1;j<=i;j++) for (k=0;k<=9;k++) { d[i][j][k]=false ; t=(10-a[i][j]) % 10; if(d[i+1][j][t]||d[i+1][j+1][t]))d[i][j][k]=true ; } 2 这样就避免了内层循环，时间复杂度为O(n)。看上去本题已经很好的解决了，但如果把加法改为乘法呢？还是a[i][j]=5和k=5的情况，需要检查的t有1,3,5,7或9五个，而不是一个。在这样的情况下，是否仍然可以避免内层循环呢？答案是肯定的，不过要稍微调整一下算法。 不妨把刚才的程序称为“综合法”，即按照一定的顺序依次计算每个状态的值。如果一个状态需要用k状态来计算（比如在刚才的例子中，一个状态需要t = 1, 3, 5, 7, 9五个状态计算），称这个状态的决策量为k。综合法的时间复杂度为O(状态个数×平均每个状态的决策数)，或O(总决策数)。对于特殊的问题，综合法并不是最好的。因为它会检查很多状态。更新法写起来更加简单，且时间效率更高： for (i=n;i>=1;i--) for (j=1;j<=i;j++) for (k=0;k<=9;k++) if(d[i][j][k]) d[i-1][j][(k*a[i-1][j])] =d[i-1][j-1][(k*a[i-1][j-1])]=true ; 虽然一个状态需要用很多状态计算，但每个状态最多只能更新两个状态。更新法就是利用这一点避免无谓的判断。更新法同时适用于取max或min的情况，但不适合于两个状态需要做运算的情况。 【例题2】最小伤害2275 【问题描述】:把儿站在一个N x N的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。 【输入数据】:第一行输入一个正整数n。以下n行描述该矩阵。矩阵中的数保证是不超过1000的正整数。 【输出数据】:输出最小伤害值。 【样例输入】: 3 1 3 3 2 2 2 3 1 2 【样例输出】:8 【数据规模】: n<=1000 【试题分析】 1、阶段和状态： f[i][j]：表示从(1,1)走到(i,j)时候的最小伤害值； 2、状态转移方程： 状态转移方程：f[i][j]=min{f[i-1][j],f[i][j-1]}+map[i][j] 初始值：f[0][i]=f[i][0]=0xfffffff; //相当于在上面和左面分别加一行和一列 answer=f[n][m] 3、核心子程序： cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf(“%ld”,&a[i][j]);//读入数据 for(i=2;i<=n;i++) {f[0][i]=0xfffffff; f[i][0]=0xfffffff;}//初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) f[i][j]=minn(f[i-1][j],f[i][j-1])+a[i][j]; cout< 【例题3】：过河卒 Description：如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。 棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C<>A，同时C<>B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 Input：键盘输入B点的坐标（n,m）以及对方马的坐标（X,Y）{不用判错} Output：屏幕输出一个整数（路径的条数）。 Sample Input：6 6 3 2 Sample Output：17 【例题4】拾垃圾的机器人 有一块地被划分成了n*m个区域，在一些区域里有垃圾要拾捡。现在科研人员开发了一个能捡垃圾的机器人，机器人每一次都可以移动一个区域的距离，假设机器人从最左上区域出发，他每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。 问：该机器人最多能够拾多少垃圾？ 在最多情况下，有多少种方案？ 【输入文件】：输入文件的第一行为两个整数n和m，接下来有一个n*m的01矩阵。矩阵中的第i行j列的数字a[i][j]=0表示为空地，a[i][j]=1表示为垃圾。 【输出文件】：输出文件的第一行为一个整数，表示该机器人拾到的最多垃圾数。第二行为一个整数，表示该机器人拾到的最多垃圾的路径总数。 【样例输入】： 6 7 0101000 0001010 0000000 0001001 0000000 0000010 【样例输出】 5 4 【数据范围】：n<=100,m<=100 【思路点拨】：我们先看样例，如图1，垃圾用G表示。假设机器人走到(i,j)这个位置，由于机器人只能向下向右走，那么机器人的上一个位置一定是(i-1,j)和(i,j-1)。 我们设机器人走到(i,j)位置时拾到最多垃圾数为f[i][j]，由于机器人只能朝右和下走，只会跟机器人上一位置拾到最多的垃圾数有关，因此很容易写出状态转移方程。 F[i][j]=max{f[i-1][j],f[i][j-1]}+a[i][j],1<=i<=n,1<=j<=m 初始值：f[0][0]=0 时间复杂度为：O(nm) 我们再来看第二问：在最优解的情况下求方案总数，我们只要每次在最优解的情况下统计路径条数即可，见图2： 设t[i][j]表示在位置(i,j)达到拾到f[i][j]垃圾时的路径总数，有如下方程： T[i][j]=t[i-1][j],当f[i][j]=f[i-1][j]+a[i][j]; (公式1) T[i][j]=t[i][j-1],当f[i][j]=f[i][j-1]+a[i][j]; (公式2) 其中公式1表示往右走能拾到最多的垃圾，公式2表示往下走能拾到最多垃圾。因此运用加法原理，综合公式1和公式2，可以写成如下形式： T[i][j]=t[i-1][j]*L+t[i][j-1]*k 当f[i][j]=f[i-1][j]+a[i][j]时，L=1，否则L=0； 当f[i][j]=f[i][j-1]+a[i][j]时，k=1，否则k=0； 初始值：t[0][0]=0 时间复杂度为：O(nm) 思考： 【例题】晴天小猪历险记之Hill bsoi1670 【例题】方格取数bsoi1265 ？两次动规 两次动规的反例： 0 100 20 0 1000 30 0 10 0 ？先搜再动规 ？两人同时取f[I,j,m,n] ? f[I,j,k] 【例题】三取方格数bsoi1720 资源分配类型DP 【例题1】机器分配2167 Description 总公司拥有高效生产设备M台，准备分给下属的N个公司。各个分公司若获得这些设备， 可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M <= 20，N <= 20。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。 Input 第一行为两个数，第一个数是设备台数M，第二个数是分公司数N。 接下来是一个N*M的矩阵，表明了第i个公司分配j台机器的盈利（都小于100）。 Output 分配这M台设备使国家所得到的盈利最大值 Sample Input 4 3 1 2 3 4 2 1 4 3 3 1 4 2 Sample Output 7 【算法分析】 1、 阶段和状态： 这是一个典型的动态规划试题。用公司数来做状态，数组f[i][j]表示前i个公司分配j台机器的最大盈利。 下标i公司数表示阶段，j机器数表示状态。题目要求的是： n个公司分配m台机器的最大盈利f[n][m]； 2、状态转移方程： f[i][j]=max{f[i-1][k]+a[i][j-k]} (1<=i<=n,1<=j<=m,0<=k<=j ) 初始值: f[0][0]=0 时间复杂度o(n*m2)3、核心子程序： 3、核心子程序： int main() { cin>>m>>n; for(i=1;i<=n;i++) for(j=1;j<=m;j++)cin>>a[i][j];//读入第i个公司分配j台机器的盈利 memset(f,0,sizeof(f)); for(i=1;i<=n;i++) //公司数 核心 for(j=1;j<=m;j++) //机器数 代码 { maxx=0; for(k=0;k<=j;k++) //决策 if(maxx