Ý tưởng Digit DP

Thay vì duyệt từng số từ ~1~ đến ~N~, ta xây dựng số từng chữ số và theo dõi:

• ~\text{pos}~: vị trí chữ số hiện tại (từ trái sang phải).
• ~\text{rem}~: tổng chữ số còn lại cần đạt (ban đầu là ~S~).
• ~\text{tight}~: true nếu các chữ số đã chọn bằng giới hạn trên ~N~.
• ~\text{started}~: true nếu đã điền chữ số khác ~0~.

Hàm đệ quy

dp(pos, rem, tight, started):
    if rem < 0: return 0
    if pos == len(digits):
        return 1 if (started and rem == 0) else 0
    limit = digits[pos] if tight else 9
    res = 0
    for d in 0..limit:
        if not started and d == 0:
            res += dp(pos+1, rem, tight and d==limit, False)
        else:
            res += dp(pos+1, rem-d, tight and d==limit, True)
    return res % MOD

Memoization

Trạng thái ~(\text{pos}, \text{rem}, \text{tight}, \text{started})~ có ~O(18 \times 162 \times 2 \times 2) \approx 11664~ trạng thái khác nhau.

Độ phức tạp

• Thời gian: ~O(\log N \times S \times 10)~
• Bộ nhớ: ~O(\log N \times S)~