Dynamic Programming21 sections · 916 units
Open in Course

Digit Set - Walkthrough

Tracing the algorithm

Count numbers 321\leq 321 using digits {1,3,5}\{1, 3, 5\}. Build digit by digit, tracking tightness. Position 00 (hundreds): if tight, try 11 and 3 (but not 5, since 5>35 > 3). If 33, stay tight. If 11, become loose. Position 11 (tens): if tight (started with 33), try 11 (becomes loose, since 1<21 < 2). If loose, try all: 11, 33, 55. Position 22 (units): if tight, try 11 (since 111 \leq 1). If loose, try all. Count all valid paths.

Answer: numbers like 111111, 113113, 115115, 131, ..., 311311, 313313, 315315 that are 321\leq 321.