Leetcode 064 最小路徑和 C Python

NO IMAGE

題目:

給定一個包含非負整數的 m x n 網格,請找出一條從左上角到右下角的路徑,使得路徑上的數字總和為最小。

說明:每次只能向下或者向右移動一步。

示例:

輸入:
[
  [1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→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];
}
};

 

但是在搜尋網上答案的時候,看到了另一種精彩的解法:

為什麼大家做動態規劃的時候都喜歡從下至上呢?可能就是因為遞迴是一種從上至下的思考方式,而動態規劃去思考的時候就容易產生這種逆向思維。

所以接下來要貼的是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];
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;
};