一、问题描述

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²)级别。

 

 

四、心得体会

我觉得这次实验课是对前几节动态规划学习的一个很好的实践、发现错误和改正错误的机会。在做单调递增最长子序列这道题时，我并没有遵循分析问题、找到最优子结构并列出递归方程、求解的步骤，代码虽然可以通过，但是并不符合要求。虽然有一些问题看似简单，只是填表就能解决。但如果不规范自己的解题习惯和步骤，容易形成不良的定性思维，在遇到复杂的问题时很难解决，因为它不是一眼就能看出解法的。正确的解题方法和步骤有助于在遇到陌生、复杂的问题时知识迁移和求解。

 

 

五、对动态规划算法的理解和体会

动态规划这个方法学得比分治法吃力，可能是它在分治的基础上又加上了最优子结构，要分别去分析各个子结构的情况。子结构一多，我就容易乱。