Triangle

Question

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

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

Thoughts

dp problem（找最小）

1. init state
2. function, 从上往下
3. last state, 最后一排最小的结果

用另一个2D array(matrix)来存过程中的结果，先全部初始化为sys.maxint, f[0][0] = triangle[0][0] 在中途会有三种情况

1. 第一个（只有上面可以到）
2. 中间的cell（可能有两种情况）
3. 最后一个（只有左上方那一个可以到）

Solution

class Solution:
    """
    @param triangle: a list of lists of integers.
    @return: An integer, minimum path sum.
    """
    def minimumTotal(self, triangle):
        # write your code here
        if not triangle:
            return None
        #get row and col numbers
        rowNum = len(triangle)
        #should be last row's col num
        colNum = len(triangle[rowNum-1])
        #inital states
        f = [[sys.maxint for i in range(colNum)] for j in range(rowNum)]
        f[0][0] = triangle[0][0]
        for i in range(1, rowNum):
            for j in range(i+1):
                if j == 0:
                    f[i][j] = f[i-1][j] + triangle[i][j]
                elif j == i:
                    f[i][j] = f[i-1][j-1] + triangle[i][j]
                else:
                    f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j]

        minTotal = sys.maxint
        for x in range(colNum):
            if minTotal > f[rowNum-1][x]:
                minTotal = f[rowNum-1][x]
        return minTotal