只能向下或者向右走,就是所在点只能由左边或者前边的点走过来,
对于当前的点就有 dp[i][j]=a[i][j]+min(dp[i-1][j],dp[i][j-1])
考虑到i=1,j=1的情况,直接对dp[1][1]赋值并且循环时跳过他,同时考虑到在i=1或者j=1时可能会越界,对二维dp数组先进行描边,大概看下数据给一个比较大的数就行。
贴上我丑丑的代码
for(int i=0;i<=n+1;i++){//描边
dp[i][0]=dp[i][m+1]=1e8;
dp[0][i]=dp[n+1][i]=1e8;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
dp[1][1]=a[1][1];
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(i==1&&j==1) continue;
dp[i][j]=a[i][j]+min(dp[i-1][j],dp[i][j-1]);
}
}