For question candies !
I ve applied DP and it is giving correct ans for smaller constrains only. How , can i think to optimise it furthure .
I mean its quite difficult to think more optimization .
Also tell me complexity for this code as a/c to me it woulb be n*k which is (10^7) and it could pass all test case .
But its not passing .
Problem with optimization
hello @Sus
No the time complexity of your solution is n * k * k.
it is because total number of distinct dp state is n*k and to make transition from one state to another u are performing this->
which is O(k) in worst case (see constraint)
thats why ur overall time complexity is O(n * k * k) which will tle .
see the video completely , bhaiya has covered the optimisation part as well.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.