题目描述
一个商人穿过一个 N×N 的正方形的网格，去参加一个非常重要的商务活动。
他要从网格的左上角进，右下角出。
每穿越中间 1 个小方格，都要花费 1 个单位时间。
商人必须在 (2N−1) 个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。
输入格式
第一行是一个整数，表示正方形的宽度 N。
后面 N 行，每行 N 个不大于 100 的正整数，为网格上每个小方格的费用。
输出格式
输出一个整数，表示至少需要的费用。
数据范围
1≤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
样例解释
样例中，最小值为 109=1+2+5+7+9+12+19+21+33。
本题思路
很简单的一道数字三角形模板题，根据题意限制了最大步数(彻底沦为板子题)：发现当矩阵大小为n*n时，恰好就是最大限制2n-1(即规约到只能向下或者向右，无法走回头路)
注意
其中只有在矩阵范围内才可以从当前位置的上面和左边更新而来(否则会出现从合法矩阵外更新而来的问题)，因为求最小由此统一初始化为极大值，且有两步一定更新
if(i == 0 && j == 0) dp[i][j] = a[i][j];
else {
dp[i][j] = INF;
if(i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i][j]);
if(j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i][j]);
}
AC_code(pull型）
#include <iostream>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n;
int a[N][N], dp[N][N];
void input() {
cin >> n;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j) cin >> a[i][j];
}
void solve() {
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
if(i == 0 && j == 0) dp[i][j] = a[i][j];
else {
dp[i][j] = INF;//极大值，有两个其中一个一定更新
if(i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i][j]);
if(j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i][j]);
}
cout << dp[n - 1][n - 1] << endl;
}
int main()
{
input();
solve();
return 0;
}
本人思路
已然看出是最熟悉不过的数字三角形模型，但在处理最小步数限制时被卡住(思考上和左走回头路的问题)，没有深层的取考虑最小步数限制这一条件，导致被卡
且遇到了只有非第一行/一列这两种情况时才可以从上一行/列转移而来的问题(导致边界值由虚拟点更新而来，偏离答案)