Solution:
Solution 1:
Define $dp_i$ as: after m operations, the length of result change from 1.
So of course for $0\leq{i}\leq{8}$, $dp_i=1$.
For $i\geq{9}$, we can plus 9 first. Then the 1 from beginning changed to 10. Now the question turn into:
- After $i-9$ operations, the length of result which change from the 1 in the first position.
- After $i-9$ operations, the length of result which change from the 0 in the second position.
And refer to the definition of $dp$, the answer of first question is $dp_{i-9}$.
And for the 0 in the second position. We can plus 10, so that we can get 10 again. And the number of operations is $i-9-10$ for the number 1. And the length is $dp_{i-9-10}$
Keep doing this until the remaining number of operations does not exceed 10. And we can get the formula below:
$$dp_i=1+dp_{i-9}+dp_{i-9-10}+dp_{i-9-10-10}+...$$
Now we just need calculate the prefix sum for every 10 operations. So that we can get the sum of $dp_{i-9-x\times{10}}$ directly.
Solution 2:
On solution 1. When we plus 10 for the 0 in the second position. But actually, we can do one operation, and change the 0 to 1. Then we can get $dp_i=dp_{i-9}+dp_{i-10}$. Much more easier.
Code
