Algorithms and Data Structures for Programming Contests

Dynamic Programming

Discussion

What is it?

Classic example: Fibonacci numbers

Why not just use recursion?

    def fib(n):
        if n == 0:  return 0
        if n == 1:  return 1
        return fib(n-1) + fib(n-2)

Problem!

    fib(5):
        fib(4):
            fib(3):
                fib(2):
                    fib(1)
                    fib(0)
                fib(1)
            fib(2):
                fib(1)
                fib(0)
        fib(3):
            fib(2):
                fib(1)
                fib(0)
            fib(1)

Solution

        def fib2(n):
            L = [0, 1]
            for i = 2,3,...,n:
                L.append(L[i-2] + L[i-1])
            return L[n]

Try it! (1)

Regroup


© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Creative Commons License Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.