Is my approach not a Brute force?
Nope, you've implemented dynamic programming
n = []
for i in range(100):
n.append(map(int,raw_input().split()))
newresult = [int(59)]
I'm not clear why you pass 59 to int, it doesn't do anything.
n.pop(0)
why didn't you do newresult = n.pop() instead of recreating the first row in the code?
for i in range(99):
x = n.pop(0)
result = list(newresult)
This makes a copy of newresult, which is pointless here since you don't keep the original around anyways
newresult =[]
t = len(x)
for j in range(t):
if(j==0):
You don't need the parens
newresult.append(result[0]+x.pop(0))
I think the code is a bit clearer if you don't use x.pop just calculate the appropriate indexes
elif(j==t-1):
newresult.append(result[0]+x.pop(0))
else:
newresult.append(max((result.pop(0)+x[0]),result[0]+x.pop(0)))
Figuring out the logic of what happens with all this popping is tricky. Again, I think calculating the index will be more straightforward. Also it'll probably be faster since popping the first element of a list is expensive.
print max(newresult)
A brute force solution would iterate over every possible path down the triangle. You are iterating over every possible position in the triangle which is much much smaller.
EDIT
The dynamic programming solutions starts with a recursive definition of the solution:
cost(i) = number(i) + max( cost(j) for j in predeccesors(i) )
Where i, j corresponds to positions on the triangle, and predecessors(i) is the set of all positions which can move onto i.
The top-down approach works by using memoization, remembering a value of cost(j) after it has been calculated. When cost(j) is needed again, it is simply reused.
However, you can also use the bottom-up approach to dynamic programming. In this case, you calculate the values of cost(i) starting from the first cells and work your way forward. Ever cost(i) only depends on the costs of cells before the current cell, and since those have already been calculated they can be reused without even using memoization.
If you look at your code, you'll find that the innermost loop is calculating the same formula as above. Furthermore, you'll find that it is calculating the cost of reach each cell starting from the cells at the top of the triangle and moving its way down. That's why I characterize it as dynamic programming.
I think you don't see this as DP, because you really didn't follow any DP logic in coming up with the solution. I think you are viewing it in terms of repeatedly reducing the complexity of the problem by eliminating the top row. In the end you are doing the same calculations as the DP version although you came at it from a different angle.
I think dp uses the same solution again and again, wheras there is
no need of such memorization here
All that's necessary for DP is to reuse solutions more than once. In this case, every number you calculate gets used in two places (one for the right, one for the left)
