3054: 最低通行费

解题思路:DP

注意事项:初始化第一行第一列数据

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10;
int g[N][N],f[N][N]; 
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++)
			cin >> g[i][j];
	for(int i = 1; i <= n; i ++) f[i][1] = f[i-1][1] + g[i][1];
	for(int i = 1; i <= n; i ++) f[1][i] = f[1][i-1] + g[1][i];
	for(int i = 2; i <= n; i ++)
		for(int j = 2; j <= n; j ++){
			f[i][j] = min(f[i-1][j],f[i][j-1]) + g[i][j];
		}
	cout << f[n][n];
	return 0;
}