LintCode (109) 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.

Have you met this question in a real interview? 

Yes

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).

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.

这个题是道老题了，可以选自顶向下，也可反过来，其实自顶向下更容易理解

DP 三板斧：

1. 求最小

2. 从某一各位移动到某一个位置 -》matrix dp

3. 列方程：

状态： f[i][j]为从[0][0] 到[i][j]的最小值

转化方程 f[i][j]= min(f[i-1][j-1], f[i-1][j])+a[i][j]. 注意corner case, 0和i=j的位置

初始化： f[0][0]=a[0][0]

结果： min(f[n-1][*])

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 32 33

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 int n=triangle.size(); vector< vector<int> > table(n, vector<int> (n, 0)); // initialize table[0][0]=triangle[0][0]; // transfer function for (int i=1; i<n; i++){ for (int j=0; j<=i; j++){ if (j>0 && j!=i){ table[i][j]=min(table[i-1][j-1], table[i-1][j])+triangle[i][j]; } else if (j==0){ table[i][j]=table[i-1][j]+triangle[i][j]; } else{ table[i][j]=table[i-1][j-1]+triangle[i][j]; } } } int result = INT_MAX; // final for (int i=0; i<n; i++){ result=min(result, table[n-1][i]); } return result; } };

这样的话是o(n^2)的空间和时间复杂度，把数组滚动一下，可以到o(n)

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 32 33

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 int n=triangle.size(); vector< vector<int> > table(2, vector<int> (n, 0)); // initialize table[0][0]=triangle[0][0]; // transfer function for (int i=1; i<n; i++){ for (int j=0; j<=i; j++){ if (j>0 && j!=i){ table[i%2][j]=min(table[(i-1)%2][j-1], table[(i-1)%2][j])+triangle[i][j]; } else if (j==0){ table[i%2][j]=table[(i-1)%2][j]+triangle[i][j]; } else{ table[i%2][j]=table[(i-1)%2][j-1]+triangle[i][j]; } } } int result = INT_MAX; // final for (int i=0; i<n; i++){ result=min(result, table[(n-1)%2][i]); } return result; } };