# Leetcode 064 最小路徑和 C Python

```輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]

dp[i][j]用來表示到達這個點所需要的最小和，它等於這個位置上的值 min(dp[i-1][j], dp[i][j-1])。

Python:

``````class Solution:
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
#動態規劃的思路
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = grid[0][0]
#第0列的所有都等於上一項加自己這項
for i in range(1, m):
dp[i][0] = dp[i-1][0]   grid[i][0]
for i in range(1, n):
dp[0][i] = dp[0][i-1]   grid[0][i]
#權衡一下，取左邊或者是上邊的最小值，畢竟我們要確定的是到[i][j]這個位置的最小和。
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j]   min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]``````

C

``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() == 0)
return 0;
int m = grid.size();
int n = grid[0].size();
m_memo = vector<vector<int>>(m 1,vector<int>(n 1,0));
//初始化邊界情況
for(int i = n-1; i >= 0;--i)
m_memo[m-1][i] = grid[m-1][i]   m_memo[m-1][i 1];
for(int j = m-1; j >= 0;--j)
m_memo[j][n-1] = grid[j][n-1]   m_memo[j 1][n-1];
for(int i = m-2; i >= 0;--i)
{
for(int j = n-2; j >= 0;--j)
{
m_memo[i][j] = grid[i][j]   min(m_memo[i][j 1], m_memo[i 1][j]);
}
}
return m_memo[0][0];
}
};``````

``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() == 0)
return 0;
int m = grid.size();
int n = grid[0].size();
m_memo = vector<vector<int>>(m 1,vector<int>(n 1,0));
//初始化邊界情況
for(int i = n-1; i >= 0;--i)
m_memo[m-1][i] = grid[m-1][i]   m_memo[m-1][i 1];
for(int j = m-1; j >= 0;--j)
m_memo[j][n-1] = grid[j][n-1]   m_memo[j 1][n-1];
return minPathSumRecusion(grid, 0, 0);
}
private:
//封裝在private裡的遞迴方法
int minPathSumRecusion(vector<vector<int>>& grid, int m, int n){
if(grid.size() == 0)
return 0;
if(m_memo[m][n] != 0)
{
return m_memo[m][n];
}
if(m == grid.size()-1 && n == grid[0].size()-1)
{
m_memo[m][n] = grid[m][n];
return m_memo[m][n];
}
if(m == grid.size()-1)
{
return m_memo[m][n];
}
if(n == grid[0].size()-1)
{
return m_memo[m][n];
}
//但是我實在不敢恭維這種思路，迴圈能做的事為什麼用遞迴去做？
m_memo[m][n] = min(grid[m][n] minPathSumRecusion(grid,m 1,n), grid[m][n] minPathSumRecusion(grid,m,n 1));
return m_memo[m][n];
}
vector<vector<int>> m_memo;
};``````