Dynamic
  Programming
 Reminder:
 Algorithmic
 Complexity                    Dynamic Programming
 What is
 dynamic                   COMP4128 Programming Challenges
 programming?
 DPonatree
 Exponential
 DP
 DPwith Data
 Structures                  School of Computer Science and Engineering
 More example                          UNSWAustralia
 problems
                  Table of Contents                                                                              2
    Dynamic
  Programming
                    1   Reminder: Algorithmic Complexity
 Reminder:
 Algorithmic
 Complexity
                    2   What is dynamic programming?
 What is
 dynamic
 programming?
 DPonatree          3   DPonatree
 Exponential
 DP                 4   Exponential DP
 DPwith Data
 Structures
 More example       5   DPwith Data Structures
 problems
                    6   More example problems
            Reminder: Algorithmic Complexity                                  3
   Dynamic
  Programming
                   The running time of your solution is important!
 Reminder:         If you don’t think about the time complexity of your
 Algorithmic       algorithm before coding it up, sooner or later you’ll end up
 Complexity
 What is           wasting a lot of time on something something that’s too
 dynamic           slow.
 programming?
 DPonatree             This is especially tragic in exam environments.
 Exponential       For simple code, analysing complexity can be as simple as
 DP                multiplying together the bounds of nested for loops.
 DPwith Data
 Structures        For recursive solutions, a rough bound is
 More example      O(time spent in recursive function ×
 problems
                                                recursion depth
                   number of recursion branches              )
                   For DP, it usually comes down to carefully determining the
                   state space and cost of recursion.
            Reminder: Algorithmic Complexity                                  4
   Dynamic
  Programming
                   On most online judges (this applies to the problem sets), a
 Reminder:         rough guideline is 50 million operations per second.
 Algorithmic
 Complexity            Constant factors occasionally matter, e.g. if you have no
 What is               recursion, or only tail-recursion, you might manage more
 dynamic
 programming?          operations than this.
 DPonatree             If you do float arithmetic, everything will be slow
 Exponential       This means that for n ≤ 1,000,000, an O(nlogn)
 DP
                   algorithm will probably run in time, but an O(n2)
 DPwith Data
 Structures        algorithm will definitely time out.
 More example
 problems          Best way to get a gauge of an online judge’s speed is to
                   submit a simple for loop and compare the number of
                   iterations it can do in 1 second to your local environment.