最小路径和

#include <iostream>
#include <vector>
using namespace std;
/**
 * 状态定义：设 dp 为大小 m×n 矩阵，其中 dp[i][j] 的值代表直到走到 (i,j) 的最小路径和.
 * 转移方程: 当前单元格 (i,j) 只能从左方单元格 (i−1,j) 或上方单元格 (i,j−1) 走到，故只需要考虑矩阵左边界和上边界.
 * 初始状态: dp 初始化.数组大小与原始数组相同. dp[0][0] = grid[0][0].
 * 返回值: 返回 dp 右下角值即最小路径和.
 */

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }
        int rows = grid.size(), columns = grid[0].size();
        /**
         * 1. 创建二维数组, 与原始数组大小相等.
         * 2. 创建 rows 行, 每行大小为 columns 的一维数组.
         */
        auto dp = vector<vector<int>>(rows, vector <int> (columns));
        // 初始化
        dp[0][0] = grid[0][0];
        // 遍历第一列
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        // 遍历第一行
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        // 遍历中间元素.其对应的路径最小和即 左边和上边取最小值加上当前元素.
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        // 返回最后一个元素
        return dp[rows-1][columns-1];

    }
};

int main() {
    vector<vector<int>> grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
    };
    Solution solution;
    int result = solution.minPathSum(grid);
    cout << result << endl;
}