[动态规划] 矩阵最小路径和

【题目描述】
    给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

输入描述
    第一行输入两个整数 n 和 m，表示矩阵的大小。
    接下来 n 行每行 m 个整数表示矩阵。

输出描述
    输出一个整数表示答案。

示例1
    输入
    4 4
    1 3 5 9
    8 1 3 4
    5 0 6 1
    8 8 4 0
    输出
    12
备注
    1≤n,m≤2000
    0≤aij ≤100

---

【代码实现 - CPP版】

#include<iostream>
#include<vector>

using namespace std;

int minPaths(vector<vector<int>> vec) {
    int row = vec.size();
    int col = vec[0].size();
    vector<vector<int>> dp(row, vector<int>(col, 0));
    dp[0][0] = vec[0][0];
    for (int i=1; i<col; i++) {
        dp[0][i] = dp[0][i-1] + vec[0][i];
    }
    
    for (int j=1; j<row; j++) {
        dp[j][0] = dp[j-1][0] + vec[j][0];
    }
    
    for (int i=1; i<row; i++) {
        for (int j=1; j<col; j++) {
            // (dp[i-1][j] >= dp[i][j-1] ? dp[i][j-1] : dp[i-1][j])
            dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + vec[i][j];
        }
    }
    return dp[row-1][col-1];
}


int main() {
    int m, n;
    cin >> m >> n;
    if ((1 > m || 2000 < m) || (1 > n || 2000 < n)) {
        cout << "Invalid input parameter(s)!" <<endl;
    }
    
    int tmp;
    bool complete = false;
    vector<vector<int>> vec(n, vector<int>(m, 0));
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> tmp;
            if (0 > tmp || 100 < tmp) {
                cout << "Invalid value, please input a correct value!" <<endl;
                break;
            }
            vec[i][j] = tmp;
            complete = true;
        }
        if (true != complete) {
            break;
        }
        complete = false;
    }
    
    cout << minPaths(vec) <<endl;
    
    return 0;
}