You are not logged in. Please login at to post your questions!


TLE for Sums in a Triangle with Memoization


I tried this code for Sums in a Triangle:

import sys
T = int(sys.stdin.readline())

memo = {}

def solve(i, j, m, limit):
    # print "i:"+str(i)
    if i==limit: 
        return 0
    if (i, j) in memo:
        # print "Reused:", i, j
        return memo[(i, j)]
    memo[(i, j)] = m[i][j] + max(solve(i+1, j, m, limit), 
                                 solve(i+1, j+1, m, limit))
    # print memo
    return memo[(i, j)]

for i in xrange(T):
    n = int(sys.stdin.readline())
    m = []
    memo = {}
    for j in xrange(n):
        m.append([int(_) for _ in (sys.stdin.readline()).split()])
    print solve(0, 0, m, n)

I save places I've visited in the matrix in a dict, so overlapping cases are taken care of, yet CC gives me a TLE. Can someone tell me what I can do to make this work?

asked 18 Apr '14, 17:28

svineet's gravatar image

accept rate: 0%

@admin help, this thread is so old!

(18 May '14, 23:42) svineet3★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 18 Apr '14, 17:28

question was seen: 2,120 times

last updated: 18 May '14, 23:42