Triangle

In [3]:

    

import sys; sys.path.append('../..'); 
from puzzles import leet_puzzle;
leet_puzzle('triangle')


    

    





Source : https://leetcode.com/problems/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.

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.







Array
Dynamic Programming

In [7]:

    

import sys


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


def minimum_path(triangle, shortest_path=None, path=None, row=0, col=0):
    
    path = path or []
    shortest_path = shortest_path or [sys.maxint]
        
    if row < len(triangle) - 1:
        path.append(triangle[row][col])
        shortest_path = minimum_path(triangle, shortest_path, path, row + 1, col)
        shortest_path = minimum_path(triangle, shortest_path, path, row + 1, col + 1)
        path.pop()

    else:
        newpath = path + [triangle[row][col]]
        if sum(newpath) < sum(shortest_path):
            shortest_path = newpath

    return shortest_path

            
p = minimum_path(input_triangle)
s = sum(p)
print p, s


    

    




 [2, 3, 5, 1] 11

In [5]:

    

%%timeit
minimum_path(input_triangle)


    

    




100000 loops, best of 3: 14.4 µs per loop