1、ACM程序设计程序设计福州大学至诚学院 冯新2023-1-11第第九讲九讲动态规划初步动态规划初步2023-1-12一、一、经典问题经典问题：数塔问题数塔问题 有形如下图所示的数塔，从顶部出发，有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大到底层，要求找出一条路径，使路径上的值最大。2023-1-13InputInput输入数据首先包括一个整数输入数据首先包括一个整数C,C,表示测试实例的个数，每个测试实例的第一行是一表示测试实例的个数，每个测试实例的第一行是一个整数个整数N(1=
2、N=100)N(1=N 109=10亿）。试想一下：试想一下：2023-1-16 拒绝拒绝暴力，暴力，倡导倡导和谐和谐2023-1-17从顶点出发时到底向左走还是向右走应取决于是从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明
3、了。直到倒数第二层时就非常明了。如数字如数字2 2，只要选择它下面较大值的结点，只要选择它下面较大值的结点1919前进就前进就可以了。所以实际求解时，可从底层开始，层层递进，可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。最后得到最大值。结论：自顶向下的分析，自底向上的计算。结论：自顶向下的分析，自底向上的计算。考虑一下：考虑一下：2023-1-18有公式：有公式：MaxSumrj=arj r=N=Max(MaxSumr+1j,MaxSumr+1j+1)+arj r=其他其他2023-1-19int main()int a100100;int sum100100;int t,i
4、,j;scanf(%d,&t);while(t-)int n;scanf(%d,&n);for(i=0;in;i+)for(j=0;j=0;i-)for(j=0;j=i;j+)sumij=aij;if(i!=n-1)sumij=max(sumi+1j,sumi+1j+1)+sumij;printf(%dn,sum00);return 0;#include int max(int a,int b)if(ab)return a;else return b;2023-1-110n许多求最优解的问题可以用动态规划来解决。用动态许多求最优解的问题可以用动态规划来解决。用动态规划解题首先要把原问题分解成若
5、干个子问题，子问规划解题首先要把原问题分解成若干个子问题，子问题的解一旦求出就被保存。题的解一旦求出就被保存。n找到子问题，就意味着找到了将整个问题逐渐分解的找到子问题，就意味着找到了将整个问题逐渐分解的办法，因为子问题可以用相同的思路分解成子问题，办法，因为子问题可以用相同的思路分解成子问题，一直分解下去，直到最底层规模最小的问题一目了然一直分解下去，直到最底层规模最小的问题一目了然看出解。每层问题的解决，会导致上层问题的解决，看出解。每层问题的解决，会导致上层问题的解决，逐层向上，就会导致整个问题的解决，我们可采取自逐层向上，就会导致整个问题的解决，我们可采取自底层的子问题开始，自底向上的
6、推导出一个个子问题底层的子问题开始，自底向上的推导出一个个子问题的解。的解。2023-1-111二、二、经典问题经典问题：最长有序子序列：最长有序子序列2023-1-112二、二、经典问题经典问题：最长有序子序列：最长有序子序列问题描述问题描述一个数的序列bi，当b1 b2 .bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,.,aN)，我们可以得到一些上升的子序列(ai1,ai2,.,aiK)，这里1=i1 i2 .iK=N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,
7、5,8).你的任务，就是对于给定的序列，求出最长上升子序列的长度。2023-1-113二、二、经典问题经典问题：最长有序子序列：最长有序子序列输入数据输入数据输入的第一行是序列的长度N(1=N=1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。输出要求输出要求最长上升子序列的长度。输入样例输入样例71 7 3 5 9 4 8输出样例输出样例42023-1-114二、二、经典问题经典问题：最长有序子序列：最长有序子序列如何把这个问题分解成子问题呢？经过分析，发现如何把这个问题分解成子问题呢？经过分析，发现 “求以求以akak（k=1,2,3Nk=1,2,3N）为终点的
8、最长上升子序列）为终点的最长上升子序列的长度的长度”是个好的子问题是个好的子问题这里把一个上升子序列这里把一个上升子序列中最右边的那个数，称为该子序列的中最右边的那个数，称为该子序列的“终点终点”。虽然。虽然这个子问题和原问题形式上并不完全一样，但是只要这个子问题和原问题形式上并不完全一样，但是只要这这N N个子问题都解决了，那么这个子问题都解决了，那么这N N个子问题的解中，最个子问题的解中，最大的那个就是整个问题的解。大的那个就是整个问题的解。MaxLenMaxLen(1)=1(1)=1MaxLenMaxLen(k)=Max (k)=Max MaxLenMaxLen(i)(i)：1i k
9、1i k 且且 aiai akak且且 k1 +1k1 +1MaxLen(kMaxLen(k)的值，就是在的值，就是在akak左边，左边，“终点终点”数值小于数值小于akak，且长度最大的那个上升子序列的长度再加，且长度最大的那个上升子序列的长度再加1 1。因为。因为akak左边任何左边任何“终点终点”小于小于akak的子序列，加上的子序列，加上akak后就能后就能形成一个更长的上升子序列。形成一个更长的上升子序列。2023-1-115解决方案：解决方案：2023-1-116#include#define MAX_N 1000int bMAX_N+10;int aMaxLenMAX_N+10;
10、int main()int N,i,j,nMax,nTmp;scanf(%d,&N);for(i=1;i=N;i+)scanf(%d,&bi);aMaxLen1=1;for(i=2;i=N;i+)/*每次求以第每次求以第i个数为终点的最长上升子序列的长度个数为终点的最长上升子序列的长度*/nTmp=0;/*记录满足条件的，第记录满足条件的，第i个数左边的上升子序列的最大长度个数左边的上升子序列的最大长度*/for(j=1;j bj)if(nTmp aMaxLenj)nTmp=aMaxLenj;aMaxLeni =nTmp+1;nMax=-1;for(i=1;i=N;i+)if(nMax aMaxLeni)nMax=aMaxLeni;printf(%dn,nMax);2023-1-117加油加油了了 2023-1-118
