题解 | 矩阵的最小路径和

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  一道区间动态规划
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
#define pre(i,j,k) for (int i = j; i < k; i++)
array<int, 2> dirx{0,1},diry{1,0};
int main() {
  ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> a(n + 1, vector<int>(m + 1, 0)), dp(n + 1, vector<int>(m + 1));
  pre(i,1,n + 1)
  	pre(j,1,m + 1)
  		cin >> a[i][j];
  pre(i, 1, n + 1)
  	dp[i][1] = a[i][1] + dp[i - 1][1];//---------对第一行进行特殊处理
  pre(j, 1, m + 1)
  	dp[1][j] = a[1][j] + dp[1][j - 1];//----------对第一列单独处理
  pre(i, 2, n + 1)
  	pre(j, 2, m + 1)
  		dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];//----------状态转移方程
  cout << dp[n][m];
}
// 64 位输出请用 printf("%lld")