C语言动态规划初步.ppt

《C语言动态规划初步.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ACM程序设计福州大学至诚学院冯新2021/10/71第九讲动态规划初步2021/10/72一、经典问题：数塔问题有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。2021/10/73Input输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1<=N<=100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内Output对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。SampleInput1573

2、8810274445265SampleOutput302021/10/74用暴力的方法，可以吗？2021/10/75这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^3>10^9=10亿）。试想一下：2021/10/76拒绝暴力，倡导和谐～2021/10/77从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第

3、二层时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。考虑一下：2021/10/78有公式：MaxSum[r][j]=a[r][j]r=N=Max(MaxSum[r+1][j],MaxSum[r+1]j+1)+a[r][j]r=其他2021/10/79intmain(){inta[100][100];intsum[100][100];intt,i,j;scanf("%d",&t);while(t--){intn;scanf("%d",&n);for(i=0

4、;i=0;i--)for(j=0;j<=i;j++){sum[i][j]=a[i][j];if(i!=n-1)sum[i][j]=max(sum[i+1][j],sum[i+1][j+1])+sum[i][j];}printf("%d",sum[0][0]);}return0;}#includeintmax(inta,intb){if(a>b)returna;elsereturnb;}2021/10/710许多求最优解的问题可以用动

5、态规划来解决。用动态规划解题首先要把原问题分解成若干个子问题，子问题的解一旦求出就被保存。找到子问题，就意味着找到了将整个问题逐渐分解的办法，因为子问题可以用相同的思路分解成子问题，一直分解下去，直到最底层规模最小的问题一目了然看出解。每层问题的解决，会导致上层问题的解决，逐层向上，就会导致整个问题的解决，我们可采取自底层的子问题开始，自底向上的推导出一个个子问题的解。2021/10/711二、经典问题：最长有序子序列2021/10/712二、经典问题：最长有序子序列问题描述一个数的序列bi，当b1

6、列(a1,a2,...,aN)，我们可以得到一些上升的子序列(ai1,ai2,...,aiK)，这里1<=i1

7、735948输出样例42021/10/714二、经典问题：最长有序子序列如何把这个问题分解成子问题呢？经过分析，发现“求以ak（k=1,2,3…N）为终点的最长上升子序列的长度”是个好的子问题――这里把一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。MaxLen(1)=1MaxLen(k)=Max{MaxLen(i)：1