Hust oj 1812 小乐乐想出门(基础dp）

35973

基础dp，状态转移方程很好想，但要注意边界处理，因为这个WA了一发

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int dp[1005][1005];
int a[1005][1005];
int Min(int y,int x)
{return x<y?x:y;
}
int main()
{int i,j,k;int n;while(cin>>n){for(i=0;i<n;i++){for(j=0;j<n;j++){cin>>a[i][j];}}dp[0][0]=a[0][0];for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==0&&j!=0)dp[i][j]=dp[i][j-1]+a[i][j];else if(j==0&&i!=0)dp[i][j]=dp[i-1][j]+a[i][j];else if(i!=0&&j!=0)dp[i][j]=Min(dp[i-1][j],dp[i][j-1])+a[i][j];//状态转移方程}}cout<<dp[n-1][n-1]<<endl;}
}