Skip to content
CCC Python Course

O(N^2) DP on intervals and centre expansion

Stage
5
Module
M5.12
Lessons
1

In this module

  • Recognize interval DP patterns and implement centre-expansion recurrences.
  • Optimize space by keeping only per-length aggregates instead of full 2D tables.
  • Handle both odd and even-length intervals in expansion.
  • Choose the right recurrence to stay in O(N^2) time on moderately sized inputs.

Before this module

M4.11Memoization and introductory dynamic programming

Lessons

  1. 1O(N^2) DP on intervals and centre expansion

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2016 J3
    Hidden Palindrome (opens on DMOJ in a new tab) DMOJ

    Count palindromic substrings using centre expansion and dynamic programming.

    Why DMOJ: An older palindrome-counting problem that still makes good practice for this module.

  2. 2023 S2
    Symmetric Mountains (opens on WMOJ in a new tab) WMOJ

    Check a sequence for a symmetric shape by expanding outward from each candidate centre.