Skip to content
CCC Python Course

Advanced DP design

Stage
6
Module
M6.7
Lessons
1

In this module

  • Combine a second dimension, such as a resource limit, with a DP state that is sorted by position.
  • Optimize DP transitions that need a window maximum with a monotonic deque.
  • Recognize when the best predecessor for a DP transition only moves forward, so a single pointer sweeps the whole array once.
  • Apply rolling arrays and tuple sorting for fast Python performance on hard S4/S5 problems.

Before this module

M4.11Memoization and introductory dynamic programmingM4.3Prefix sums (1D, 2D, prefix/suffix max)M6.11Monotonic stack and deque

Lessons

  1. 1Advanced DP design

Practice

Try these on the judge. Each link opens the problem on DMOJ.

  1. 2019 S4
    Tourism (opens on DMOJ in a new tab) DMOJ

    Plan a multi-day itinerary that visits the most cities under a travel budget.

  2. 2015 S5
    Greedy For Pies (opens on DMOJ in a new tab) DMOJ

    Split a set of pies among people so that the smallest share is as large as possible.