Can anyone tell me OPTIMIZE APPROACH for 369 Numbers Question

[ashuthe1]

question link : https://www.spoj.com/problems/NUMTSN/

[simes]

I’ve not solved this problem, but it looks like a Digit DP to me.