# Triangle - Find the minimum path sum from top to bottom ### Source - lintcode: [(109) Triangle](http://www.lintcode.com/en/problem/triangle/) ~~~ Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. Note Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. Example For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). ~~~ ### 題解 題中要求最短路徑和，每次只能訪問下行的相鄰元素，將triangle視為二維坐標。此題方法較多，下面分小節詳述。 ### Method 1 - Traverse without hashmap 首先考慮最容易想到的方法——遞歸遍歷，逐個累加所有自上而下的路徑長度，最后返回這些不同的路徑長度的最小值。由于每個點往下都有2條路徑，使用此方法的時間復雜度約為 O(2n)O(2^n)O(2n), 顯然是不可接受的解，不過我們還是先看看其實現思路。 ### C++ Traverse without hashmap ~~~ class Solution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ int minimumTotal(vector<vector<int> > &triangle) { if (triangle.empty()) { return -1; } int result = INT_MAX; dfs(0, 0, 0, triangle, result); return result; } private: void dfs(int x, int y, int sum, vector<vector<int> > &triangle, int &result) { const int n = triangle.size(); if (x == n) { if (sum < result) { result = sum; } return; } dfs(x + 1, y, (sum + triangle[x][y]), triangle, result); dfs(x + 1, y + 1, (sum + triangle[x][y]), triangle, result); } }; ~~~ ### 源碼分析 `dfs()`的循環終止條件為`x == n`，而不是`x == n - 1`，主要是方便在遞歸時sum均可使用`sum + triangle[x][y]`，而不必根據不同的y和y+1改變，代碼實現相對優雅一些。理解方式則變為從第x行走到第x+1行時的最短路徑和，也就是說在此之前并不將第x行的元素值計算在內。 這種遍歷的方法時間復雜度如此之高的主要原因是因為在n較大時遞歸計算了之前已經得到的結果，而這些結果計算一次后即不再變化，可再次利用。因此我們可以使用hashmap記憶已經計算得到的結果從而對其進行優化。 ### Method 2 - Divide and Conquer without hashmap 既然可以使用遞歸遍歷，當然也可以使用「分治」的方法來解。「分治」與之前的遍歷區別在于「分治」需要返回每次「分治」后的計算結果，下面看代碼實現。 ### C++ Divide and Conquer without hashmap ~~~ class Solution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ int minimumTotal(vector<vector<int> > &triangle) { if (triangle.empty()) { return -1; } int result = dfs(0, 0, triangle); return result; } private: int dfs(int x, int y, vector<vector<int> > &triangle) { const int n = triangle.size(); if (x == n) { return 0; } return min(dfs(x + 1, y, triangle), dfs(x + 1, y + 1, triangle)) + triangle[x][y]; } }; ~~~ 使用「分治」的方法代碼相對簡潔一點，接下來我們使用hashmap保存triangle中不同坐標的點計算得到的路徑和。 ### Method 3 - Divide and Conquer with hashmap 新建一份大小和triangle一樣大小的hashmap，并對每個元素賦以`INT_MIN`以做標記區分。 ### C++ Divide and Conquer with hashmap ~~~ class Solution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ int minimumTotal(vector<vector<int> > &triangle) { if (triangle.empty()) { return -1; } vector<vector<int> > hashmap(triangle); for (int i = 0; i != hashmap.size(); ++i) { for (int j = 0; j != hashmap[i].size(); ++j) { hashmap[i][j] = INT_MIN; } } int result = dfs(0, 0, triangle, hashmap); return result; } private: int dfs(int x, int y, vector<vector<int> > &triangle, vector<vector<int> > &hashmap) { const int n = triangle.size(); if (x == n) { return 0; } // INT_MIN means no value yet if (hashmap[x][y] != INT_MIN) { return hashmap[x][y]; } int x1y = dfs(x + 1, y, triangle, hashmap); int x1y1 = dfs(x + 1, y + 1, triangle, hashmap); hashmap[x][y] = min(x1y, x1y1) + triangle[x][y]; return hashmap[x][y]; } }; ~~~ 由于已經計算出的最短路徑值不再重復計算，計算復雜度由之前的 O(2n)O(2^n)O(2n)，變為 O(n2)O(n^2)O(n2), 每個坐標的元素僅計算一次，故共計算的次數為 1+2+...+n≈O(n2)1+2+...+n \approx O(n^2)1+2+...+n≈O(n2). ### Method 4 - Dynamic Programming 從主章節中對動態規劃的簡介我們可以知道使用動態規劃的難點和核心在于**狀態的定義及轉化方程的建立**。那么問題來了，到底如何去找適合這個問題的狀態及轉化方程呢？ 我們仔細分析題中可能的狀態和轉化關系，發現從`triangle`中坐標為 triangle[x][y]triangle[x][y]triangle[x][y] 的元素出發，其路徑只可能為 triangle[x][y]?>triangle[x+1][y]triangle[x][y]->triangle[x+1][y]triangle[x][y]?>triangle[x+1][y] 或者 triangle[x][y]?>triangle[x+1][y+1]triangle[x][y]->triangle[x+1][y+1]triangle[x][y]?>triangle[x+1][y+1]. 以點 (x,y)(x,y)(x,y) 作為參考，那么可能的狀態 f(x,y)f(x,y)f(x,y) 就可以是： 1. 從 (x,y)(x,y)(x,y) 出發走到最后一行的最短路徑和 1. 從 (0,0)(0,0)(0,0) 走到 (x,y)(x,y)(x,y)的最短路徑和 如果選擇1作為狀態，則相應的狀態轉移方程為：f1(x,y)=min{f1(x+1,y),f1(x+1,y+1)}+triangle[x][y]f_1(x,y) = min\{f_1(x+1, y), f_1(x+1, y+1)\} + triangle[x][y]f1(x,y)=min{f1(x+1,y),f1(x+1,y+1)}+triangle[x][y] 如果選擇2作為狀態，則相應的狀態轉移方程為：f2(x,y)=min{f2(x?1,y),f2(x?1,y?1)}+triangle[x][y]f_2(x,y) = min\{f_2(x-1, y), f_2(x-1, y-1)\} + triangle[x][y]f2(x,y)=min{f2(x?1,y),f2(x?1,y?1)}+triangle[x][y] 兩個狀態所對應的初始狀態分別為 f1(n?1,y),0≤y≤n?1f_1(n-1, y), 0 \leq y \leq n-1f1(n?1,y),0≤y≤n?1 和 f2(0,0)f_2(0,0)f2(0,0). 在代碼中應注意考慮邊界條件。下面分別就這種不同的狀態進行動態規劃。 ### C++ From Bottom to Top ~~~ class Solution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ int minimumTotal(vector<vector<int> > &triangle) { if (triangle.empty()) { return -1; } vector<vector<int> > hashmap(triangle); // get the total row number of triangle const int N = triangle.size(); for (int i = 0; i != N; ++i) { hashmap[N-1][i] = triangle[N-1][i]; } for (int i = N - 2; i >= 0; --i) { for (int j = 0; j < i + 1; ++j) { hashmap[i][j] = min(hashmap[i + 1][j], hashmap[i + 1][j + 1]) + triangle[i][j]; } } return hashmap[0][0]; } }; ~~~ ### 源碼分析 1. 異常處理 1. 使用hashmap保存結果 1. 初始化`hashmap[N-1][i]`, 由于是自底向上，故初始化時保存最后一行元素 1. 使用自底向上的方式處理循環 1. 最后返回結果hashmap[0][0] 從空間利用角度考慮也可直接使用triangle替代hashmap，但是此舉會改變triangle的值，不推薦。 ### C++ From Top to Bottom ~~~ class Solution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ int minimumTotal(vector<vector<int> > &triangle) { if (triangle.empty()) { return -1; } vector<vector<int> > hashmap(triangle); // get the total row number of triangle const int N = triangle.size(); //hashmap[0][0] = triangle[0][0]; for (int i = 1; i != N; ++i) { for (int j = 0; j <= i; ++j) { if (j == 0) { hashmap[i][j] = hashmap[i - 1][j]; } if (j == i) { hashmap[i][j] = hashmap[i - 1][j - 1]; } if ((j > 0) && (j < i)) { hashmap[i][j] = min(hashmap[i - 1][j], hashmap[i - 1][j - 1]); } hashmap[i][j] += triangle[i][j]; } } int result = INT_MAX; for (int i = 0; i != N; ++i) { result = min(result, hashmap[N - 1][i]); } return result; } }; ~~~ #### 源碼解析 自頂向下的實現略微有點復雜，在尋路時需要考慮最左邊和最右邊的邊界，還需要在最后返回結果時比較最小值。