动态规划实验报告

一、问题描述

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

 

 

四、心得体会

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

 

 

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

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

 

上一篇:牛血清白蛋白BSA:蛋白定量检测标准品


下一篇:1308 统计单词数量