Minimum Path Sum · 數據結構與算法/leetcode/lintcode題解

# Minimum Path Sum - tags: [[DP_Matrix](# "根據動態規劃解題的四要素，矩陣類動態規劃問題通常可用 f[x][y] 表示從起點走到坐標(x,y)的值")] ### Source - lintcode: [(110) Minimum Path Sum](http://www.lintcode.com/en/problem/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. ~~~ ### 題解 1. State: f[x][y] 從坐標(0,0)走到(x,y)的最短路徑和 1. Function: f[x][y] = (x, y) + min{f[x-1][y], f[x][y-1]} 1. Initialization: f[0][0] = A[0][0], f[i][0] = sum(0,0 -> i,0), f[0][i] = sum(0,0 -> 0,i) 1. Answer: f[m-1][n-1] 注意最后返回為f[m-1][n-1]而不是f[m][n]. 首先看看如下正確但不合適的答案，OJ上會出現[TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")。未使用hashmap并且使用了遞歸的錯誤版本。 ### C++ [dfs](# "Depth-First Search, 深度優先搜索") without hashmap: ~~Wrong answer~~ ~~~ class Solution { public: /** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */ int minPathSum(vector<vector<int> > &grid) { if (grid.empty()) { return 0; } const int m = grid.size() - 1; const int n = grid[0].size() - 1; return helper(grid, m, n); } private: int helper(vector<vector<int> > &grid_in, int x, int y) { if (0 == x && 0 == y) { return grid_in[0][0]; } if (0 == x) { return helper(grid_in, x, y - 1) + grid_in[x][y]; } if (0 == y) { return helper(grid_in, x - 1, y) + grid_in[x][y]; } return grid_in[x][y] + min(helper(grid_in, x - 1, y), helper(grid_in, x, y - 1)); } }; ~~~ 使用迭代思想進行求解的正確實現： ### C++ Iterative ~~~ class Solution { public: /** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */ int minPathSum(vector<vector<int> > &grid) { if (grid.empty() || grid[0].empty()) { return 0; } const int M = grid.size(); const int N = grid[0].size(); vector<vector<int> > ret(M, vector<int> (N, 0)); ret[0][0] = grid[0][0]; for (int i = 1; i != M; ++i) { ret[i][0] = grid[i][0] + ret[i - 1][0]; } for (int i = 1; i != N; ++i) { ret[0][i] = grid[0][i] + ret[0][i - 1]; } for (int i = 1; i != M; ++i) { for (int j = 1; j != N; ++j) { ret[i][j] = grid[i][j] + min(ret[i - 1][j], ret[i][j - 1]); } } return ret[M - 1][N - 1]; } }; ~~~ ### 源碼分析 1. 異常處理，不僅要對grid還要對grid[0]分析 1. 對返回結果矩陣進行初始化，注意ret[0][0]須單獨初始化以便使用ret[i-1] 1. 遞推時i和j均從1開始 1. 返回結果ret[M-1][N-1]，注意下標是從0開始的此題還可進行空間復雜度優化，和背包問題類似，使用一維數組代替二維矩陣也行，具體代碼可參考 [水中的魚: [LeetCode] Minimum Path Sum 解題報告](http://fisherlei.blogspot.sg/2012/12/leetcode-minimum-path-sum.html) 優化空間復雜度，要么對行遍歷進行優化，要么對列遍歷進行優化，通常我們習慣先按行遍歷再按列遍歷，有狀態轉移方程 f[x][y] = (x, y) + min{f[x-1][y], f[x][y-1]} 知，想要優化行遍歷，那么f[y]保存的值應為第x行第y列的和。由于無行下標信息，故初始化時僅能對第一個元素初始化，分析時建議畫圖理解。 ### C++ 1D vector ~~~ class Solution { public: /** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */ int minPathSum(vector<vector<int> > &grid) { if (grid.empty() || grid[0].empty()) { return 0; } const int M = grid.size(); const int N = grid[0].size(); vector<int> ret(N, INT_MAX); ret[0] = 0; for (int i = 0; i != M; ++i) { ret[0] = ret[0] + grid[i][0]; for (int j = 1; j != N; ++j) { ret[j] = grid[i][j] + min(ret[j], ret[j - 1]); } } return ret[N - 1]; } }; ~~~ 初始化時需要設置為`INT_MAX`，便于`i = 0`時取`ret[j]`.