1. 算法第三章上机实践报告

1.1 问题描述

一个商人穿过一个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。

1.2 算法描述

由于该问题的最优解依赖于子问题的最优解，因此具有最优子结构性质，因此运用动态规划法，构建两个矩阵，a矩阵记录每个格子的费用，mf（MinFee）矩阵记录从起点到达该方格的最小费用

解决此问题需要注意原题限制条件“商人必须在(2N-1)个单位时间穿越出去”，在该限制条件下商人若要到达右下角的终点方向只能为→或↓，由此可推得：

mf[i][j]依赖于mf[i-1][j]或mf[i][j-1]；

mf矩阵中第一行中满足：mf[1][j]=mf[1][j-1]+a[1][j]；//第一行除第一个以外的所有元素依赖于左边的元素

mf矩阵中第一列满足：mf[i][1]=mf[i-1][1]+a[i][1]；//第一列除第一个以外的所有元素依赖于上面的元素

且mf[1][1]=a[1][1]；

代码如下：

#include<iostream>
using namespace std;
int a[101][101],mf[101][101];	//a[i][j]记录对应方格的费用，mf数组记录从起点到达mf[i][j]时的最小费用，即备忘录数组 
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) {
    	for(int j=1; j<=n; j++) {
    		cin>>a[i][j];
		}
	}
	
    for(int i=1; i<=n; i++) {	//初始化第一列 
    	mf[i][1] = mf[i-1][1] + a[i][1];
	}
	
    for(int j=1; j<=n; j++) {	//初始化第一行 
    	mf[1][j] = mf[1][j-1] + a[1][j];  
	}
	
    for(int i=2; i<=n; i++){
    	for(int j=2; j<=n; j++) {
			mf[i][j] = min(mf[i-1][j], mf[i][j-1]) + a[i][j];
		}
	}
	
    cout<<mf[n][n]<<endl;
}

1.3 问题求解

1.3.1 根据最优子结构性质，列出递归方程

mf[1][1] = a[1][1]//边界条件
mf[1][j] = mf[1][j-1] + a[1][j], j>1
mf[i][1] = mf[i-1][1] + a[i][1], i>1
mf[i][j] = max{mf[i-1][j],mf[i][j-1]}+a[i][j], i>1, j>1

1.3.2 表的维度，填表范围和填表顺序

表的维度：二维

填表范围：i（1...n）j（1...n）

填表顺序：从左到右，从上到下

1.3.3 该算法的时间复杂度和空间复杂度

时间复杂度：由于存在两个循环的嵌套，所以时间复杂度为O(n^2)

空间复杂度：该算法使用了二维数组，所以空间复杂度为O(n^2)

1.4 心得体会

通过本次实践课的习题练习，我发现解决动态规划问题时必须首先明确问题的最优子结构性质，通过大问题和小问题的关系写出递推方程，并必须明确边界条件，再通过代码实现才能解决问题，本次上机实践对如何解决动态规划问题的流程有了大致的了解和初步的掌握，但是在解决难度较大的问题时仍然存在许多困难，仍需要多加练习和耕耘。

2. 对动态规划问题的理解和体会

解决动态规划问题需要对题目的问题有深刻的理解，需要首先找到最优子结构和边界条件，因为动态规划问题中最大问题的最优解是依赖于子问题的最优解的，大问题的解与子问题的解层层相扣，最终归于边界条件，因此只有明确了边界条件和递推方程才能解决动态规划问题。动态规划问题多种多样，但它们都具有相同的填表格式，因此在动态规划问题中填表是非常重要的一环，如果掌握了填表的方法和技巧，便会在解题过程中轻松许多。