动态规划实验报告
- 格式：pdf
- 大小：120.42 KB
- 文档页数：3
动态规划实验报告
⼀、问题描述
7-3 最低通⾏费 (25 分)
⼀个商⼈穿过⼀个N×N的正⽅形的⽹格，去参加⼀个⾮常重要的商务活动。他要从⽹格的左上⾓进，右下⾓出。每穿越中间1个⼩⽅格，都
要花费1个单位时间。商⼈必须在(2N-1)个单位时间穿越出去。⽽在经过中间的每个⼩⽅格时，都需要缴纳⼀定的费⽤。
这个商⼈期望在规定时间内⽤最少费⽤穿越出去。请问⾄少需要多少费⽤？
注意：不能对⾓穿越各个⼩⽅格（即，只能向上下左右四个⽅向移动且不能离开⽹格）。
输⼊格式:
第⼀⾏是⼀个整数，表⽰正⽅形的宽度N (1≤N<100)；
后⾯N⾏，每⾏N个不⼤于100的整数，为⽹格上每个⼩⽅格的费⽤。
输出格式:
⾄少需要的费⽤。
输⼊样例:
51 4 6 8 102 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²)级别。
四、⼼得体会
我觉得这次实验课是对前⼏节动态规划学习的⼀个很好的实践、发现错误和改正错误的机会。在做单调递增最长⼦序列这道题时，我并没有
遵循分析问题、找到最优⼦结构并列出递归⽅程、求解的步骤，代码虽然可以通过，但是并不符合要求。虽然有⼀些问题看似简单，只是填
表就能解决。但如果不规范⾃⼰的解题习惯和步骤，容易形成不良的定性思维，在遇到复杂的问题时很难解决，因为它不是⼀眼就能看出解
法的。正确的解题⽅法和步骤有助于在遇到陌⽣、复杂的问题时知识迁移和求解。
五、对动态规划算法的理解和体会
动态规划这个⽅法学得⽐分治法吃⼒，可能是它在分治的基础上⼜加上了最优⼦结构，要分别去分析各个⼦结构的情况。⼦结构⼀多，我就
容易乱。
