一、题目大意
从左上角进去,从右下角出来,每穿过一个小方格,就要消耗一单位的时间。
商人必须要在\(2*n-1\)的时间内,穿到右下角去。每经过一个小方格,都需要缴纳一定的费用,问我们总花费最小是多少?
二、题目分析
摘花生的题与这道题特别相似,摘花生是从左上走到右下角,只能是向下或者向右走,不能回头走,问我们摘到的最大值是多少?
这道题要求在\(2*n-1\)的时间内,从左上角走到右下角,最小花费是多少?
理解一下这个\(2*n-1\),如果我们不走回头路的话,那么需要走\(2*n-1\)步,所以消耗的时间为\(2*n-1\)单位时间。
换句话说,就是只能向右或向下走,不能向左或向上,否则不能在\(2*n-1\)步中走到右下角。
分析完\(2*n-1\),就明白这道题其实就是摘花生那道题,只不过不是求最大值,而是求最小值即可。
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int w[N][N];
int f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> w[i][j];
/*base case
本题的初始化有典型意义,就是二维环境下,可以初始化第一行和第一列
根据题意,其实就是前缀和的含义
总结:在处理base case时,一定要结合题意进行思考,这个地方容易出错,但也容易想明白
*/
//第一行,每个位置都是直接从左侧过来费用最小
for (int i = 1; i <= n; i++)f[1][i] = f[1][i - 1] + w[1][i];
//第一列,每个位置都是直接从上面过来费用最小
for (int i = 1; i <= n; i++)f[i][1] = f[i - 1][1] + w[i][1];
//第一行第一列讨论完,剩下的可以愉快的递推了~
//左上角到右下角,f[i][j]依赖的是f[i-1][j]和f[i][j-1],所以正序遍历正好符合题意
for (int i = 2; i <= n; i++)
for (int j = 2; j <= n; j++)
f[i][j] = min(f[i][j - 1], f[i - 1][j]) + w[i][j];
//输出
printf("%d \n", f[n][n]);
return 0;
}