made by Jaehyeok Choi

dynamic programming

Increasing number include same number. (ex. 0000, 00011122333388)

0 can be added only after the number ends with 0.

1 can be added only after the number ends with 0 or 1.

Following these sequences, I though keep checking the end number of increasing number will work.

I made a dp and save the number of end number of all possible increasing number.

n = 1

index 0 1 2 ... 9 number 1 1 1 ... 1 prev array

When n is 2, 0 can be added to the number ends with 0, so index 0 value will always 0. 1 will be added to the number ends with the 0 and 1, so add index 0 value + index 1 value. 2 will be added to the number ends with the 0,1 and 2, so add index 0 value + 1 value + 2 value.

However, I alreay added the index 0 value + index 1 value in the current array[i-1] adding it with index 2 value in the previous array with it will work.

index 0 1 2 ... 9 number 1 2 3 ... 9 in here 3 is not adding (prev[index0] + prev[index1] + prev[index2]) it is adding ( prev[2] + index[2-1])

I use sliding window to save the space complexity.

You can contact me through email, which is [email protected]. Thank you for visiting this github!