算法第三章实验报告

实验内容: 动态规划的应用

第一题

题目描述：

7-3 最低通行费 (25 分)

一个商人穿过一个N×N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

输入格式:

第一行是一个整数，表示正方形的宽度N (1≤N<100)；

后面N行，每行N个不大于100的整数，为网格上每个小方格的费用。

输出格式:

至少需要的费用。

输入样例:

5

1  4  6  8  10

2  5  7  15 17

6  8  9  18 20

10 11 12 19 21

20 23 25 29 33

结尾无空行

输出样例:

109

结尾无空行

样例中，最小值为109=1+2+5+7+9+12+19+21+33。

解题思路：改问题求解的是一个通行费用的最优解，目的是为了让穿过路费尽可能的少。分析可得，从第一个格子到第n各格子的最少通行费等于经过第一个格子的路费加上从第二个格子到第n个格子的最优解。由此可得，该问题包含最优子结构问题，因此我们可以用动态规划法来求解这个最优解。

题目分析：

（1） 该动态规划法的边界条件：m[i][1]=m[i][1]+m[i-1][1](i=2;i<=N;i++) m[1][j]=m[1][j]+m[1][j-1](j=2;j<=N; j++)  

（2） 递归表达式：m[i][j]=min(m[i][j]+m[i-1][j],m[i][j]+m[i][j-1]);

（3） 最优解在数组m[N][N]的位置，因此应采用从左到右，从上到下的方式来计算最优解

代码实现：

#include <iostream>

using namespace std;

int N;

int m[1000][1000];

int dp(){

// m[1][1]=m[1][1];

for(int i=2;i<=N;i++){

m[i][1]=m[i][1]+m[i-1][1];

}

for(int j=2;j<=N;j++){

    m[1][j]=m[1][j]+m[1][j-1];

}

for(int i=2;i<=N;i++){

for(int j=2;j<=N;j++){

m[i][j]=min(m[i][j]+m[i-1][j],m[i][j]+m[i][j-1]);

}

}

return m[N][N];

}

int main(int argc, char** argv) {

cin>>N;

for(int i=1;i<=N;i++){

for(int j=1;j<=N;j++){

cin>>m[i][j];

}

}

cout<<dp();

return 0;

}

第二题

题目描述：

7-1 最大子段和 (25 分)

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

输入格式:

输入有两行：

第一行是n值（1<=n<=10000)；

第二行是n个整数。

输出格式:

输出最大子段和。

输入样例:

在这里给出一组输入。例如：

6

-2 11 -4 13 -5 -2

结尾无空行

输出样例:

在这里给出相应的输出。例如：

20

解题思路：

该题目的在于求解一个数组的最大字段和，数组里面的数可正可负，因此最大字段和可能从数组的某一个元素开始，故要求解最大字段和需求解从每一个数组元素开头的最大字段和，从而得到整个数组的最大字段和。由此我们也可以发现该问题存在最优子结构，故可以用动态规划法来求解。

题目分析：

（1） 动态规划递归式：b[j]=max{b[j-1]+a[j],a[j]}

（2） 用一个变量记下最大的字段和，计算完成后该变量即为最优解。

代码实现：

#include <iostream>

using namespace std;

int N;

int a[1000];

int MaxSum(){

int sum = 0;

for(int i=1;i<=N;i++){

int tmp = 0;

for(int j=i;j<=N;j++){

tmp += a[j];

if(tmp>sum){

sum=tmp;

}

}

}

return sum;

}

int main(int argc, char** argv) {

cin>>N;

for(int i=1;i<=N;i++){

cin>>a[i];

}

cout<<MaxSum();

return 0;

}

第三题

题目描述：

7-2 单调递增最长子序列 (25 分)

设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

输入格式:

输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开

输出格式:

最长单调递增子序列的长度

输入样例:

在这里给出一组输入。例如：

5

1 3 5 2 9

结尾无空行

输出样例:

在这里给出相应的输出。例如：

4

解题思路：

该题求解一个数组中最长的单调递增子序列，最长单调子序列可以是数组的任意一个元素开始的，因此该数组的最长单调子序列而可以通过求解以其中某一个元素开头的最长单调子序列来解决，因此可以用动态规划法。

题目分析：

（1） 边界条件，a[i]=a[i]，d[N]=1;

（2） 递归表达式：d[i]=d[j]+1;

代码实现：#include <iostream>

using namespace std;

int a[1000];

int d[1000];

int N;

int dp(){

d[N]=1;

for(int i=N-1;i>=1;i--){

for(int j=i+1;j<=N;j++){

if(a[i]<=a[j]&&d[j]+1>d[i]){

d[i]=d[j]+1;

}

}

}

int max=0;

for(int i=1;i<=N;i++){

if(d[i]>max){

max=d[i];

}

}

return max;

}

int main(int argc, char** argv) {

cin>>N;

for(int i=1;i<=N;i++){

cin>>a[i];

}

cout<<dp();

return 0;

}

第四题

题目描述：

7-4 编辑距离问题 (25 分)

设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。

输入格式:

第一行是字符串A，文件的第二行是字符串B。

提示：字符串长度不超过2000个字符。

输出格式:

输出编辑距离d(A,B)

输入样例:

在这里给出一组输入。例如：

fxpimu

xwrs

结尾无空行

输出样例:

在这里给出相应的输出。例如：

5

解题思路：

该题的目的是求解令字符串B变成字符串A所需要的最少编辑次数。编辑操作共有三种，删除，插入和替换。每一次操作都应该是有利于B变成A的。

题目分析:

（1） 边界条件，当A、B中有一个字符串为空，则一个字符串要变成另一个字符串只需进行B长度的删除或A长度的插入

（2） 递归表达式：int k = min (c[i-1][j] + 1, c[i][j-1] + 1);

代码实现：

#include<iostream>

#include<string.h>

using namespace std;

char a[20000], b[20000];

int c[20000][20000];

int main()

{

 cin >> a;

 cin >> b;

 int la = strlen(a), lb = strlen(b), count = 1;

 for (int i=0;i<=la;i++) c[i][0] = i;

 for (int i=0;i<=lb;i++) c[0][i] = i;//两种极端情况

 for (int i=1;i<=la;i++)

 {

  for (int j=1;j<=lb;j++)

  {

   if (a[i-1] == b[j-1]) count = 0;

   else count = 1;

   int k = min (c[i-1][j] + 1, c[i][j-1] + 1);

   c[i][j] = min (k, c[i-1][j-1] + count);

  }

 }

 cout << c[la][lb];

 return 0;

}

关于动态规划法的学习心得和体会：

动态规划法主要是考察编程者对问题的分析和理解是否到位，如果能够正确分析出一个问题的最优解的求解方法，求解过程中的计算顺序以及能够推导出正确的递归表达式就可以求解出最优解。