Problem Statement: https://codeforces.com/problemset/problem/1036/C
So, in classy number we can uniquely determine particular state by 3 parameters such as: (position, count, tight)
position: this parameter signifies in which position I’m currently at in the string of numbers.
count: this parameter signifies that the particular number is classy number or not by applying the condition count<=3
tight: this parameter signifies that the number should not go beyond the maximum limit of a number.
So, my dp table will be like dp[20][5][2]
And Space Complexity will be (20x5x2)
Now the Doubt is that:
What will be the time complexity of the problem!!
So, from my understanding Time Compelxity of this problem is looks like this:
Time Complexity= (No. of States) x Transition Time
i.e. T(n)=S(n) + Transition Time
And Transition Time is that number of states on which a particular DP state is dependent.
So, is it mean, overlapping subproblems?
But from my understanding, there will be no overlapping subproblems in this problem.
So, I don’t get, what Transition Time means. And I need help on this problem.
Thank You.