原題
Description
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
Notice
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
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).
解題
我們先忽略Notice的空間限制，采用動態(tài)規(guī)劃來解決這道題。
因為從上到下遍歷的話需要判斷很多邊界條件，為了方便我們從下至上遍歷整個三角形。
狀態(tài)轉(zhuǎn)移方程（從下至上遍歷）：
dp[x][y] = min( dp[x+1][y], dp[x+1][y+1] ) + triangle[x][y]
解釋：
從下至上走，每個位置的最短路徑，是下一行的兩個可選格子中比較小的，加上這個位置上的值。
其中最后一行的每個位置的最短路徑，其實就是自己位置上的值。
我們只需要首先構(gòu)建一個和triangle一樣大的dp數(shù)組，
然后dp的最后一行直接賦予triangle最后一行的值（最后一行的最短路徑就是值）
再根據(jù)這個狀態(tài)轉(zhuǎn)移方程，從下至上遍歷整個三角形，計算出整個dp數(shù)組，就可以得到答案。
代碼
class Solution {
public:
/*
* @param triangle: a list of lists of integers
* @return: An integer, minimum path sum
*/
int minimumTotal(vector<vector<int>> triangle) {
// write your code here
// dp數(shù)組完全復制一個triangle，有兩個好處
// 1. dp的大小和triangle完全一致
// 2. 順便復制了triangle的最后一行
vector<vector<int>> dp(triangle);
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j < triangle[i].size(); j++) {
// 根據(jù)狀態(tài)轉(zhuǎn)移方程計算整個dp
dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
// 頂端為答案
return dp[0][0];
}
};
空間復雜度O(n)
題目還有一個額外加分是，空間負責度控制在O(n)，其中n為triangle的行數(shù)，當然我們也可以理解為triangle最后一行的元素數(shù)量。
回顧剛剛動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程
dp[x][y] = min( dp[x+1][y], dp[x+1][y+1] ) + triangle[x][y]
我們可以發(fā)現(xiàn)，計算時，只需要依賴上一次計算的結(jié)果。
計算最終結(jié)果（第一行）的時候，我們只需要第二行的兩個位置的最短路徑；
計算第二行的時候，我們只需要第三行三個位置的最短路徑；
最終計算倒數(shù)第二行的時候，我們只需要最后一行的n個位置的最短路徑。
上述過程中，需要的最長的行就是最后一行，一共n的元素。
也就是說，只需要一個長度為n的數(shù)組，就可以存下所有所需的計算結(jié)果。
狀態(tài)轉(zhuǎn)移方程變?yōu)椋?/p>
dp[i] = min( dp[i], dp[i+1] ) + triangle[x][y]
代碼
class Solution {
public:
/*
* @param triangle: a list of lists of integers
* @return: An integer, minimum path sum
*/
int minimumTotal(vector<vector<int>> triangle) {
// write your code here
// 直接復制triangle的最后一行，兩個好處
// 1. 長度正好為n
// 2. 最后一行的值就是這行各個位置的最短路徑
vector<int> dp(triangle.back());
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j < triangle[i].size(); j++) {
// 根據(jù)狀態(tài)轉(zhuǎn)移方程計算dp
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
}
}
// 第一個元素為答案
return dp[0];
}
};
