Skip to content
CCC Python Course

DP with hash maps (prefix-sum-keyed DP)

Stage
7
Module
M7.7
Lessons
1

In this module

  • Recognize when a DP transition depends on the prefix sum seen at an earlier position.
  • Use a dictionary keyed by prefix sum instead of an array indexed by sum.
  • Apply mean-shift to turn a target-average question into a zero-sum question.
  • Count subarrays that match a target using a prefix-sum hash map.

Before this module

M6.7Advanced DP designM4.3Prefix sums (1D, 2D, prefix/suffix max)M4.1Hash-based lookup

Lessons

  1. 1DP with hash maps

Practice

Try this on the judge. The link opens the problem on WMOJ.

  1. 2024 S5
    Chocolate Bar Partition (opens on WMOJ in a new tab) WMOJ

    Split a bar of chocolate squares into two groups of equal weight.