import unittest
import utils


# O(n^2) time. O(n^2) space. DP.
class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        n = len(triangle)

        # dp[i][j]: the minimum path sum to reach triangle[i][j]
        dp = [[0] * (i + 1) for i in xrange(n)]

        for i in xrange(n):
            for j in xrange(i + 1):
                dp[i][j] = triangle[i][j]

                if i >= 1:
                    prev = 0x7FFFFFFF
                    if j >= 1:
                        prev = dp[i - 1][j - 1]
                    if j < i:
                        prev = min(prev, dp[i - 1][j])
                    dp[i][j] += prev

        return min(dp[-1])


class Test(unittest.TestCase):
    def test(self):
        cases = utils.load_json_from_path('../leetcode_test_cases/p120.json').test_cases

        for case in cases:
            actual = Solution().minimumTotal(case.triangle)
            self.assertEqual(case.expected, actual)


if __name__ == '__main__':
    unittest.main()

@@ -46,18 +46,16 @@
  O(n
-%5E2
 ) space.
  DP.
@@ -50,16 +50,32 @@
 ) space.
+ Space-optimized
  DP.%0Acla
@@ -326,22 +326,24 @@
 p = 
-%5B
 %5B0%5D * 
-(i + 1)
+n%0A%0A       
  for
@@ -357,18 +357,17 @@
 range(n)
-%5D%0A
+:
 %0A       
@@ -367,35 +367,38 @@
         
-for i in xrange(n):
+    prev = 0x7FFFFFFF%0A
 %0A       
@@ -442,24 +442,20 @@
         
-dp%5Bi%5D%5Bj%5D
+curr
  = trian
@@ -496,46 +496,8 @@
  1:%0A
-                    prev = 0x7FFFFFFF%0A
     
@@ -517,20 +517,19 @@
    if j 
-%3E= 1
+%3C i
 :%0A      
@@ -557,24 +557,24 @@
 v = 
-dp%5Bi - 1%5D%5Bj - 1%5D
+min(prev, dp%5Bj%5D)
 %0A   
@@ -590,34 +590,30 @@
         
-if j %3C i:%0A        
+curr += prev%0A%0A
         
@@ -631,36 +631,14 @@
 v = 
-min(prev, dp%5Bi - 1%5D%5Bj%5D)%0A    
+dp%5Bj%5D%0A
     
@@ -656,21 +656,17 @@
  dp%5B
-i%5D%5B
 j%5D 
-+
 = 
-prev
+curr
 %0A%0A  
@@ -688,12 +688,8 @@
 n(dp
-%5B-1%5D
 )%0A%0A%0A

120. Triangle