# 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;
}
};
~~~
#### 源码解析
自顶向下的实现略微有点复杂，在寻路时需要考虑最左边和最右边的边界，还需要在最后返回结果时比较最小值。
- Preface
- Part I - Basics
- Basics Data Structure
- String
- Linked List
- Binary Tree
- Huffman Compression
- Queue
- Heap
- Stack
- Set
- Map
- Graph
- Basics Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bucket Sort
- Counting Sort
- Radix Sort
- Basics Algorithm
- Divide and Conquer
- Binary Search
- Math
- Greatest Common Divisor
- Prime
- Knapsack
- Probability
- Shuffle
- Basics Misc
- Bit Manipulation
- Part II - Coding
- String
- strStr
- Two Strings Are Anagrams
- Compare Strings
- Anagrams
- Longest Common Substring
- Rotate String
- Reverse Words in a String
- Valid Palindrome
- Longest Palindromic Substring
- Space Replacement
- Wildcard Matching
- Length of Last Word
- Count and Say
- Integer Array
- Remove Element
- Zero Sum Subarray
- Subarray Sum K
- Subarray Sum Closest
- Recover Rotated Sorted Array
- Product of Array Exclude Itself
- Partition Array
- First Missing Positive
- 2 Sum
- 3 Sum
- 3 Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Merge Sorted Array
- Merge Sorted Array II
- Median
- Partition Array by Odd and Even
- Kth Largest Element
- Binary Search
- Binary Search
- Search Insert Position
- Search for a Range
- First Bad Version
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Median of two Sorted Arrays
- Sqrt x
- Wood Cut
- Math and Bit Manipulation
- Single Number
- Single Number II
- Single Number III
- O1 Check Power of 2
- Convert Integer A to Integer B
- Factorial Trailing Zeroes
- Unique Binary Search Trees
- Update Bits
- Fast Power
- Hash Function
- Count 1 in Binary
- Fibonacci
- A plus B Problem
- Print Numbers by Recursion
- Majority Number
- Majority Number II
- Majority Number III
- Digit Counts
- Ugly Number
- Plus One
- Linked List
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Duplicates from Unsorted List
- Partition List
- Two Lists Sum
- Two Lists Sum Advanced
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle II
- Reverse Linked List
- Reverse Linked List II
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Reorder List
- Copy List with Random Pointer
- Sort List
- Insertion Sort List
- Check if a singly linked list is palindrome
- Delete Node in the Middle of Singly Linked List
- Rotate List
- Swap Nodes in Pairs
- Remove Linked List Elements
- Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- Binary Tree Maximum Path Sum
- Lowest Common Ancestor
- Invert Binary Tree
- Diameter of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Subtree
- Binary Tree Zigzag Level Order Traversal
- Binary Tree Serialization
- Binary Search Tree
- Insert Node in a Binary Search Tree
- Validate Binary Search Tree
- Search Range in Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- Binary Search Tree Iterator
- Exhaustive Search
- Subsets
- Unique Subsets
- Permutations
- Unique Permutations
- Next Permutation
- Previous Permuation
- Unique Binary Search Trees II
- Permutation Index
- Permutation Index II
- Permutation Sequence
- Palindrome Partitioning
- Combinations
- Combination Sum
- Combination Sum II
- Minimum Depth of Binary Tree
- Word Search
- Dynamic Programming
- Triangle
- Backpack
- Backpack II
- Minimum Path Sum
- Unique Paths
- Unique Paths II
- Climbing Stairs
- Jump Game
- Word Break
- Longest Increasing Subsequence
- Palindrome Partitioning II
- Longest Common Subsequence
- Edit Distance
- Jump Game II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Distinct Subsequences
- Interleaving String
- Maximum Subarray
- Maximum Subarray II
- Longest Increasing Continuous subsequence
- Longest Increasing Continuous subsequence II
- Graph
- Find the Connected Component in the Undirected Graph
- Route Between Two Nodes in Graph
- Topological Sorting
- Word Ladder
- Bipartial Graph Part I
- Data Structure
- Implement Queue by Two Stacks
- Min Stack
- Sliding Window Maximum
- Longest Words
- Heapify
- Problem Misc
- Nuts and Bolts Problem
- String to Integer
- Insert Interval
- Merge Intervals
- Minimum Subarray
- Matrix Zigzag Traversal
- Valid Sudoku
- Add Binary
- Reverse Integer
- Gray Code
- Find the Missing Number
- Minimum Window Substring
- Continuous Subarray Sum
- Continuous Subarray Sum II
- Longest Consecutive Sequence
- Part III - Contest
- Google APAC
- APAC 2015 Round B
- Problem A. Password Attacker
- Microsoft
- Microsoft 2015 April
- Problem A. Magic Box
- Problem B. Professor Q's Software
- Problem C. Islands Travel
- Problem D. Recruitment
- Microsoft 2015 April 2
- Problem A. Lucky Substrings
- Problem B. Numeric Keypad
- Problem C. Spring Outing
- Microsoft 2015 September 2
- Problem A. Farthest Point
- Appendix I Interview and Resume
- Interview
- Resume