Isn't this dynamic programming?

Question

I was solving problem 18 and 67 on Project Euler and came up with an algorithm that actually goes through almost all the possibilities to find the answer in O(n) time. However, ProjecEuler claims that a Brute force solution will take too long. Many have implemented this problem using trees, dp and what not.

Is my approach not a Brute force?

n = []
for i in range(100):
 n.append(map(int,raw_input().split()))
newresult = [int(59)]
n.pop(0)
for i in range(99):
 x = n.pop(0)
 result = list(newresult)
 newresult =[]
 t = len(x)
 for j in range(t):
 if(j==0):
 newresult.append(result[0]+x.pop(0))
 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)))
print max(newresult)

UPDATE: here's a idea how my algorithm works (taking max when needed) enter image description here

• Leonid: Since you seem to understand how dynamic programming works, would you kindly describe your algorithm using words?
• nischayn22: @Leonid checkout the update :)

Answer 1

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)

• Leonid: "Nope, you've implemented dynamic programming" - it does not look like one at first, but I guess it is. One would have to review the definition of the dynamic programming. Obviously, standard dp approach that works in reverse direction is easier to comprehend, but I am curious whether this is another technique for solving problems that I have not encountered yet, or just an over-complication of something that is easy. Perhaps it makes solutions to some other problems easier ...
• nischayn22: @Winston your explanation is appreciated, however I am more concerned of the technique and less of the code (let it be dirty its just for projectEuler). Can you explain why this is dp? I think dp uses the same solution again and again, wheras there is no need of such memoization here
• Winston Ewert: @nischayn22, see edit.
• nischayn22: +1 for the edit, I will try to see if this approach can be used in other dp problems