<p>Given a <code>m x n</code> <code>grid</code> filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.</p>

<p><strong>Note:</strong> You can only move either down or right at any point in time.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> grid = [[1,3,1],[1,5,1],[4,2,1]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> Because the path 1 &rarr; 3 &rarr; 1 &rarr; 1 &rarr; 1 minimizes the sum.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,2,3],[4,5,6]]
<strong>Output:</strong> 12
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 200</code></li>
</ul>

using vi = vector<int>;
using vii = vector<vi>;

class Solution {

    const int INF = 987654321;

public:
    int minPathSum(vector<vector<int>>& grid);
    // int findMinPath(vii &grid, int MSIZE, int NSIZE, int m, int n);
};

int Solution::minPathSum(vector<vector<int>>& grid) {

    // 입력
    // 양의 정수로 채워진 MxN 그리드

    // 문제
    // 좌상단에서 우하단까지의 경로 탐색
    // 단, 경로상 모든 수치 비용 최소화
    // 매번 아래 혹은 우측만 이동 가능

    // 출력
    // 최소 비용 출력

    const int MSIZE = grid.size();
    const int NSIZE = grid[0].size();

    // Top-Down Recursive Implementation
    // const int minCost = findMinPath(grid, MSIZE, NSIZE, MSIZE-1, NSIZE-1);

    for (int r=0; r<MSIZE; r++) {
        for (int c=0; c<NSIZE; c++) {

            if (r-1 < 0 && c-1 < 0) { continue; }
            
            const int lhs = (r-1 < 0)? INF:grid[r-1][c];
            const int rhs = (c-1 < 0)? INF:grid[r][c-1];

            grid[r][c] = grid[r][c] + min(lhs, rhs);

        }
    }

    return grid[MSIZE-1][NSIZE-1];

}

// int Solution::findMinPath(vii &grid, int MSIZE, int NSIZE, int m, int n) {

//     if (m < 0 || m >= MSIZE) { return INF; }
//     if (n < 0 || n >= NSIZE) { return INF; }

//     if (m == 0 && n == 0) { return grid[m][n]; }

//     const int lResult = findMinPath(grid, MSIZE, NSIZE, m, n-1);
//     const int tResult = findMinPath(grid, MSIZE, NSIZE, m-1, n);

//     const int minResult = grid[m][n] + min(lResult, tResult);

//     return minResult;

// }
12400