TLE for Sums in a Triangle with Memoization

general
, , ,
1

Hi,

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?

2

@admin help, this thread is so old!