Leetcode[120] Triangle
08 Nov 2015###Task1 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.
###Python ####O(n2) space
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
depth = len(triangle)
dp = [[0 for i in range(depth)] for j in range(depth)]
for i in range(depth)[::-1]:
for j in range(i + 1):
if i == depth - 1:
dp[i][j] = triangle[i][j]
else:
dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
return dp[0][0]
####O(n) space
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
depth = len(triangle)
dp = triangle[depth - 1]
for i in range(depth - 1)[::-1]:
for j in range(i + 1):
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
return dp[0]
###Java
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return -1;
}
int depth = triangle.size();
int[][] f = new int[depth][depth];
for (int i = 0; i < depth; i++) {
f[depth - 1][i] = triangle.get(depth - 1).get(i);
}
for (int i = depth - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle.get(i).get(j);
}
}
return f[0][0];
}
}
###Points
每个元素需要维护一次，总共有1+2+…+n=n*(n+1)/2个元素，所以时间复杂度是O(n^2)
- Bottom up is easier: don’t need to take care of index out of bound