算法设计与分析——3

第三章实验报告

7-3 最低通行费

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 = 1+2+5+7+9+12+19+21+33

2. 算法描述

   主要思路:到终点的最小费用依赖于到其上方和左方最小费用,不断推至起点,因此采用动态规划使用n^2大小的备忘录记录左上各个方格的最小费用。

   int minfee[1000][1000] = {0};

   int MinFee(int n, int a[1000][1000]) {
     // 第一行第一列无需判断从上面来还是从左边来
     for (int i = 1; i <= n; i++) {
       minfee[i][1] = a[i][1] + minfee[i-1][1];
     }
     for (int j = 1; j <= n; j++) {
       minfee[1][j] = a[1][j] + minfee[1][j-1];
     }
     // 从第二行第二列开始需要在上和左中选择最小的
     for (int i = 2; i <= n; i++) {
       for (int j = 2; j <= n; j++) {
         if (minfee[i][j-1] < minfee[i-1][j])    minfee[i][j] = a[i][j] + minfee[i][j-1];    // 左边
         else minfee[i][j] = a[i][j] + minfee[i-1][j];    // 上边
       }
     }
     return minfee[n][n];    // 返回终点的最小值
   }

 

3. 时间复杂度分析

   填表时,使用二重循环,时间复杂度为O(n^2)。

4. 空间复杂度分析

   引入二维数组minfee,空间复杂度为O(n^2)。

5. 心得体会

   此次实验课,通过小组形式写代码,代码需要更多地上手写,在写的过程中发现具体问题,而不能只靠纸上分析,过多的讨论只会让思路越来越不清晰,代码也一行没打。

   这道题是动态规划中使用备忘录的典型例子:

   与分治法有点点类似,都是将一个规模较大的问题,分解为规模较小的子问题,但是动态规划的子问题并非相互独立,而是相互依赖重叠的,因此我们借用备忘录记录已解子问题,后续只需查表,避免了重复计算,提高效率,多用于求最优子结构,最优解问题,除此之外,我们还需注意填表的方式,如从上向下,自底向上,有可能只填上三角等等。

上一篇:js中的定时器


下一篇:第四章第二次作业四件套