Tracking Aggregates Inside DP States

Track auxiliary aggregates (min in window, parity) alongside DP index to know legality of transitions.

Why this shows up in the real world

Loan underwriting tracks rolling debt ratios while DP scores approval paths.

Core idea (explained for students)

Augment state with (i, running_sum mod k) when problem needs modular balance.

Try this in Python

def count_subseq_divisible(nums: list[int], k: int) -> int:
    dp = [0] * k
    dp[0] = 1
    for x in nums:
        ndp = dp[:]
        for r in range(k):
            nr = (r + x) % k
            ndp[nr] = (ndp[nr] + dp[r]) % (10**9 + 7)
        dp = ndp
    return dp[0]


print(count_subseq_divisible([1, 2, 3, 4, 5], 3))

Common mistakes

• Exploding state when mod k large.
• Losing history that matters later.

Key takeaways

• Only augment with values that appear in transition predicates.