[benjamincburns]

Edit:

Doh - I'm a moron! You're using a recurrence relation, which has the nice property of never computing the same sub-solution twice. I'll leave this here as a reminder to think before I nitpick next time.

Original:

Apologies to nitpick, but your iterative python solution isn't DP. DP hinges on the idea of never computing the answer to the same problem twice. For it to be DP, it would need to memoize subproblem solutions and refer to the solution cache rather than recompute the solution to every subproblem in the tree every time.

This solution fits the bill, although it can probably be written a bit more elegantly:

  fibs = {0: 1, 1: 1}
  def fib(n):
      global fibs
      stack = []
      for a in xrange(n,0,-1):
          if a in fibs:
              stack.reverse()
              for item in stack:
                  fibs[item] = fibs[a] + fibs[a-1]
                  a = item
              break
          else:
              stack.append(a)
      return fibs[n]