算法第三章上机实验报告

1. 实践报告任选一题进行分析。内容包括：

1.1 问题描述：

一个商人穿过一个N×N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

1.2 算法描述：

本题求最优解，最优解依赖于最优子解，运用递归求出最优子解后即可求出最优解。代码如下：

#include <iostream>

#include <cstdio>

#define N 101

using namespace std;

int f[N][N], a[N][N], n;

int ans;

int main() {

    scanf("%d", &n);

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= n; j++) {

            scanf("%d", &a[i][j]);

            if(i == 1) f[i][j] = a[i][j] + f[i][j-1];

            if(j == 1) f[i][j] = a[i][j] + f[i-1][j];

        }

    for(int i = 2; i <= n; i++)

        for(int j = 2; j <= n; j++) f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];

    printf("%d\n", f[n][n]);

    return 0;

   }

1.3 问题求解：

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

f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];

当只有一个方格时，f[i][j]= f[1][1]

1.1.2 给出填表法中表的维度、填表范围和填表顺序

二维，i从1到n且j从1到n,从左至右从上至下

1.1.3 分析该算法的时间和空间复杂度

时间复杂度：二重循环，O（2^n）

空间复杂度：O（2^n）

1.3 心得体会（对本次实践收获及疑惑进行总结）

本次实验加强我分析问题的能力，有时候抽象的的问题可以具体化，一步步分析，从子问题一步步延伸到最后的问题。实验过程中易忽略边界值（为1）的定义而导致实现最后答案经历坎坷，在与同伴的讨论和老师的指点中修改了对边界条件的界定。

2. 你对动态规划算法的理解和体会

首先应该理清思路，写出正确的递归方程式，反复检查是否与题意相符合，根据递归方程式求出最优子解，进而求出最优解。填表法需注意顺序及边界条件的界定，胆大心细。