动态规划_leetcode120(经典的梯形模式)

class Solution1(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        self.dp(triangle)

        # i
        # i , i+1


    def dp(self,triangle):

        length = len(triangle)
        memo = [-1 for i in range(length)]


        for i in range(length-1,-1,-1):

            if i == length-1:

                for j in range(len(triangle[i])):
                    memo[j] = triangle[i][j]

            else:
                temp = memo[0:]

                for j in  range(len(triangle[i])):

                    memo[j] = min(temp[j],temp[j+1])+triangle[i][j]

        print memo[0]

        return memo[0]








class Solution2(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        pass


s = Solution1()

t = [
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

s.minimumTotal(t)