AcWing 1018. 最低通行费
原题链接
简单
作者:
永远向前
,
2021-08-20 09:53:25
,
所有人可见
,
阅读 265
//1 必须在2*n - 1 的时间内出去
//走一格子 花费 1时间
//2 想要花费最小的费用
//每个格子都有必须要花的费用
// 观察发现 商人只能向右走和向下走 只要向左或者向上走就一定会超过规定的时间
//最后一步
//dp[i][j] 的含义是从(1,1) 到(n,n) 所需要的最小花费
//一定是从左边或者上边下来的
//dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + a[i][j];
#include<iostream>
using namespace std;
const int N = 110;
int a[N][N];
int dp[N][N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin>>a[i][j];
for(int i=1;i<=n;i++)
dp[i][0] = 0x3f3f3f3f;
for(int i=1;i<=n;i++)
dp[0][i] = 0x3f3f3f3f;
dp[1][1] = a[1][1];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if(i==1&&j==1)
continue;
else
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + a[i][j];
cout<<dp[n][n]<<'\n';
return 0;
}