一、问题描述
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。
二、算法描述
仔细分析商人的走法,商人在每一格时,其实只有两种选择,要么向右走,要么向下走;他不可能向上走或者向左走,因为那只会离位于右下角的目的地越来越远,而且还白白花费更多的钱。
假设商人站在 [i][j] 格上,他只有两种可能的来路,要么从左边 [i][j-1] 走过来,要么从上面 [i-1][j] 走过来。第一种情况,假设商人是从左边 [i][j-1] 走过来的,那么他的上一步只能是:要么从 左边的 [i][j-2] 格子过来,要么从上面的 [i-1][j-1] 格子过来。第二种情况,假设假设商人是从上面 [i-1][j] 走过来的,那么他的上一步只能是:要么从左边的 [i-1][j-1] 格子过来,要么从 [i-2][j] 过来。
综上,我们可以总结出,商人站在任意一个格子时,只能有两种情况,从左边或者从上面来,而到底是从哪里来的,就取决于这两种来路哪个的累积价格更少。所谓累积价格,就是从左上角的入口走到当前格子所花费的总费用。
根据以上分析,我们不难发现,这个问题具有最优子结构性质,即当前问题的最优解依赖于子问题的最优解。
三、问题求解
1、根据最优子结构的性质,列出递归方程
初始化两个数组,arr数组用于记录每个格子的费用。rec数组用于记录走到当前格子所花费的最少费用:
int arr[101][101] = { 0 };
int rec[101][101];
递归方程如下:
rec[i][j] = min(rec[i][j - 1], rec[i - 1][j]) + arr[i][j];
它的含义是:取左边来的总费用和上面来的总费用中较少的那一个,再加上当前格子要花费的费用,就是从入口走到当前格子的最少费用。
2、给出填表法中表的维度、填表范围和填表顺序
创建一个变量n,用于记录正方形网格的数量(n*n):int n = 0; cin >> n;
将每个格子的费用填入arr二维数组:
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> arr[i][j];
}
}
这里为了便于理解和阅读,舍弃掉第一行和第一列,从arr[1][1]开始填表。
初始化统计费用总和的数组rec:
for (int i = 0; i <= n; i++)
{
rec[i][0] = 20000;
}
for (int j = 0; j <= n; j++)
{
rec[0][j] = 20000;
}
仍采取了舍弃第一行和第一列,从rec[1][1]开始填表。
有一点需要注意的是,当商人位于正方形的第一行和第一列时,他不可能从左边或者上面来,我们给rec数组初始化的时候,要给rec[i][0]和rec[o][j]设置一个极大的不可能的值,保证在调用递归方程时,只能取唯一的那条来路。题目给定的每个小方格的费用不大于100,所以设置一个比100大很多的数就可以了。
由于是从[1][1]开始填表,要一直填到[n][n],填rec表的范围就是1~n、1~n。
分析递归方程:rec[i][j] = min(rec[i][j - 1], rec[i - 1][j]) + arr[i][j];
每个格子的费用只与它左边和上面格子有关,所以填表的顺序就是从左到右、从上到下。
代码实现如下:
int dp()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == 1 && j == 1)
{
rec[i][j] = arr[i][j];
}
else
{
rec[i][j] = min(rec[i][j - 1], rec[i - 1][j]) + arr[i][j];
}
}
}
return rec[n][n];
}
最终,rec[n][n]记录的就是整个问题的最优解,即最少费用。
3、时间和空间复杂度
由于在填表时,使用了两层循环,所以时间复杂度是O(n²)级别。
在求解问题时,所需要的额外两个数组的大小是随着正方形的大小n变化的,因此空间复杂度是O(n²)级别。
四、心得体会
我觉得这次实验课是对前几节动态规划学习的一个很好的实践、发现错误和改正错误的机会。在做单调递增最长子序列这道题时,我并没有遵循分析问题、找到最优子结构并列出递归方程、求解的步骤,代码虽然可以通过,但是并不符合要求。虽然有一些问题看似简单,只是填表就能解决。但如果不规范自己的解题习惯和步骤,容易形成不良的定性思维,在遇到复杂的问题时很难解决,因为它不是一眼就能看出解法的。正确的解题方法和步骤有助于在遇到陌生、复杂的问题时知识迁移和求解。
五、对动态规划算法的理解和体会
动态规划这个方法学得比分治法吃力,可能是它在分治的基础上又加上了最优子结构,要分别去分析各个子结构的情况。子结构一多,我就容易乱。