题目描述
首先很一定的是当前这格的状态是由它上面一格和左边一格推出来的(只能往右边或者下边走,不然就超时了)
仔细思考了一下,发现我只需要利用当前算到的方格的费用和上一个状态就能把当前状态给算出来;
令状态转移方程为f[];
就会发现未更新的f[j]就是这一格上面那一格的,而f[j-1]是它左边一格的。
结合上面所说的,我们可以边输入边算答案,最后输出f[n]即可。
温馨提示:由于是算最小值,所以不要忘了初始化f[]为1e9(当然还需要一个入口f[1]
C++ 代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int f[110];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
f[0] = 1e9;
for(int i = 2;i <= n;i ++) f[i] = 1e9;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= n;j ++)
{
int x;
cin>>x;
f[j] = min(f[j],f[j - 1]) + x;
}
}
cout<<f[n];
}