leetcode | Minimum Path Sum

Minimum Path Sum : https://leetcode.com/problems/minimum-path-sum/

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

Note: You can only move either down or right at any point in time.

解析：

本題是一個動态規劃類型的題目，

求 grid[0][0] 到 grid[rows-1][cols-1]的最小路徑和

設m[i][j]表示從grid[0][0]到grid[i][j]的最小路徑和，那麼

m[0][0] = grid[0][0];

m[0][j] = m[0][j-1] + grid[0][j];

m[i][0] = m[i-1][0] + grid[i][0];

m[i][j] = min(m[i-1][j], m[i][j-1]) + gird[i][j];

由上述條件等式，easy寫出動态規劃的程式：