小分析:
尽管题目说可以上下左右都走,但是分析限制条件:$2n - 1$ ,事实上只有不走回头路才能是 $2n-1$,也就是不能往上或者往左
所以应该想到摘花生那道题的状态方程f[i][j] = max(f[i - 1][j] + w[i][j], f[i][j - 1] + w[i][j])
注意: 摘花生是求最大值, 这道题是求最小值,需要考虑边界问题。
所以这里分开写状态方程比较好考虑
if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]); // 只有不在第一行时才可以从上面过来
if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]); // 只有不在第一列时才可以从左边过来
我写成这样也通过了耶
f[0][j] = f[i][0] = INF;
f[i][j] = min(f[i][j - 1] + w[i][j], f[i - 1][j] + w[i][j]);
还有:记得特判左上角!
#include<iostream>
#include<algorithm>
#include <cstring>
using namespace std;
const int N = 110, INF = 1e9;
int n;
int w[N][N], f[N][N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
scanf("%d", &w[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
if (i == 1 && j == 1) f[i][j] = w[i][j];
else
{
f[i][j] = INF;
if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
}
}
printf("%d\n", f[n][n]);
return 0;
}