Count numbers with constrained digits using tight/loose states
Traverse digits most-significant to least with a 'tight' flag and memoize (pos, tight, state...).
Use for counting numbers ≤ N with properties (e.g., no consecutive ones, digit sums).
Constrain next digit when tight
from functools import lru_cache
def count_no_consec_ones(n):
s = bin(n)[2:]
@lru_cache(None)
def dp(i, tight, prev1):
if i == len(s): return 1
up = int(s[i]) if tight else 1
total = 0
for d in range(up + 1):
if prev1 and d == 1: continue
total += dp(i+1, tight and d==up, d==1)
return total
return dp(0, True, False)Carry state like prev digit/sum
from functools import lru_cache
def count_digits_sum_leq(n, target):
s=str(n)
@lru_cache(None)
def dp(i, tight, sum_):
if i==len(s): return 1 if sum_<=target else 0
up = int(s[i]) if tight else 9
total=0
for d in range(up+1):
total += dp(i+1, tight and d==up, sum_+d)
return total
return dp(0, True, 0)def template(*args, **kwargs):
# General template placeholder
passDigits times state size.
Memo table size.