基本解法
题目描述
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
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).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.
题目大意是：给定一个数字组成的三角形，要求从顶层到底层，找到一条最小路径。使得在这条路径上所有数之和是所有路径中最小的。往下一层走时，你只能访问到与当前位置相邻的两个数。
算法分析
利用动态规划的思想可以很快的解决问题。对于每一层的每一个数，都可以有一个值minValue，代表“从顶层开始到这里结束的最小路径和”。而这个值显然是“当前数值”与“左上方数的minValue”或“右上方数的minValue”之和。即状态方程如下：1
minValue[current] = min{ minValue[left_top], minValue[right_top] } + currentValue
于是，设置一个数组minValue用于记录最小路径和，每个点的坐标以行号row和行中的序号num表示，则其最小路径和为minValue[row * (row + 1) / 2 + num]。从顶层开始遍历，计算出每一个minValue[x]的值，最后找到底层最小的一个值，便是想要的答案。
代码实现
代码实现如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int rowNum = triangle.size();
int totalNum = rowNum * (rowNum + 1) / 2;
int* minValue = new int[totalNum] { 0 };
minValue[0] = triangle[0][0];
for (int row = 1; row < rowNum; row++) {
for (int num = 0; num < triangle[row].size(); num++) {
int left = 200000, right = 200000;
if (num - 1 >= 0) {
left = minValue[getIndex(row - 1, num - 1)] + triangle[row][num];
}
if (num <= row - 1) {
right = minValue[getIndex(row - 1, num)] + triangle[row][num];
}
minValue[getIndex(row, num)] = left < right ? left : right;
}
}
int min = 200000;
for (int i = 0; i < rowNum; i++) {
if (minValue[getIndex(rowNum - 1, i)] < min) {
min = minValue[getIndex(rowNum - 1, i)];
}
}
return min;
}
private:
int getIndex(int row, int num) {
return (row * (row + 1) / 2 + num);
}
};
优化方案
然而，题目中给出了一个加分项：只用O(n)的额外空间来解题（n为行数），而上述解法中，对每一个数值的minValue进行了保存，实际的额外空间为O(n*(n+1)/2)。
算法分析
如何只是用O(n)的额外空间呢？显然，我们在动态规划的过程中，是以行为一个单位进行的。而实际上每计算出当前行的所有minValue值，上一行的值就已经没有意义，不需要保留了。因此，实际上我们只需要一个长度为n的数组来保存数据，n是最长的行的长度，也是行数。
代码实现
Discuss中的一个解法如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int n = triangle.size();
vector<int> minlen(triangle.back());
for (int layer = n-2; layer >= 0; layer--) // For each layer
{
for (int i = 0; i <= layer; i++) // Check its every 'node'
{
// Find the lesser of its two children, and sum the current value in the triangle with it.
minlen[i] = min(minlen[i], minlen[i+1]) + triangle[layer][i];
}
}
return minlen[0];
}
};
这里采用了从底层到底层的构造顺序。每一层记录minValue只采用了一个长度为n的数组，达成了目标。
本文为博主原创文章，转载请注明出处。