第三章上机实践报告

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

1.1 问题描述

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

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

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

1.2 算法描述

#include
#include
using namespace std;
const int N=100;
int a[N][N],b[N][N];
int main()
{
int i,j,n;
cin>>n;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=2;i<=n;i++){
b[0][i]=b[i][0]=10000000; //边界
}

for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
b[i][j]=min(b[i-1][j],b[i][j-1])+a[i][j]; //递归
}
}
cout<}

1.3 问题求解：

该问题要求最优解，而最优解与子问题的最优解有关，找出递归公式用带备忘录的递归方法求解。

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

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

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

填表维度·：二维列表

填表范围：从第二行二列开始

填表顺序：从左到右从上到下

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

时间复杂度：因为有两个for循环从1到n所有时间复杂度为o（n*2）

空间复杂度：需要两个n行n列的二维数组来储存所以其空间复杂度为o（n*2）

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

对于动态规划问题找出递归方程式以及分析填表的顺序，表的边界很重要。

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

动态规划算法的思想就是把大问题化为小问题
找到小问题的解决方案，合成大问题的解决方案，记录小问题的最优解决方案，以便于回溯寻找，降低时间复杂度。