//
// Created by 罗炳国 on 2024/1/8.
//

#ifndef PFJ_CODE045_MINPATHSUM_H
#define PFJ_CODE045_MINPATHSUM_H

#include "commonHeader.h"

/**
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 * 64.https://leetcode.cn/problems/minimum-path-sum/description/
 * */

class code045_minPathSum {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<int> dp(m, 0);

        dp[m - 1] = grid[n - 1][m - 1];
        for (int i = m - 2; i >= 0; i--)
            dp[i] = grid[n - 1][i] + dp[i + 1];

        for (int i = n - 2; i >= 0; i--) {
            dp[m - 1] = dp[m - 1] + grid[i][m - 1];
            for (int j = m - 2; j >= 0; j--)
                dp[j] = grid[i][j] + min(dp[j], dp[j + 1]);
        }
        return dp[0];
    }

    void test() {
        vector<vector<int>> grid {{1, 3, 1},{1, 5, 1},{4, 2, 1}};
        int ans = minPathSum(grid);
        std::cout << ans << endl;

        grid = {{1, 2, 3}, {4, 5, 6}};
        ans = minPathSum(grid);
        std::cout << ans << endl;

        grid = {{1, 2, 5}, {3, 2, 1}};
        ans = minPathSum(grid);
        std::cout << ans << endl;
    }
};


#endif//PFJ_CODE045_MINPATHSUM_H