we need: how many numbers is less than or equal m and contains exactly [count] lucky digits. if state is DP[position][less][count] so cnt[k] = DP[0][false][k] were k is number of lucky digits.

we start from left to right and use digits that we can.

for example let m is 53237

we start from left:

if we choose [0 to 4] for first digit (leftmost digit), for next digits we are free to use all digits [0-9] because we are sure that all next numbers will be less than m. so we set [less] flag true. and answer is:

DP[position][less][count] = Sigma{ DP[position + 1][true][count — (if we use lucky digit ? 1 : 0)] } for all digits we can use

but if we choose 5 for first digit, for next digit we can only use [0-3] so [less] flag remains false. so answer is:

DP[position][less][count] = Sigma{ DP[position + 1][false][count — (if we use lucky digit ? 1 : 0)] } for all digits we can use

at the end if [position] == |m|:

DP[position][less][count] = (count == 0 ? 1 : 0)

sorry for poor English!