Recursion & DP Target: 15s
Bottom-up on triangle: each cell picks the smaller child. 1D array suffices since we overwrite left to right.
def minimumTotal(triangle):
dp = triangle[-1][:] # start from bottom row
for i in range(len(triangle) - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
return dp[0]Type it from memory. Go.