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!