Is my code correct ?
and what will be its time complexity.
my code = https://ide.codingblocks.com/s/292883
Optimal game strategy dp
You can submit your code and check if it passes all the test cases.
Search for question "Optimal Game Strategy II " .It must be there in the challenges.
The complexity of this problem is O(n^2)
My code has been submitted successfully.
But I unable to understand complexity of this problem O(n^2).Please go through the code I used memoization technique.
Help !!!
heyy, waiting for your reply
Since you have used a 2d array as the memo table of size n x n.While recursing, you would fill this table. So simply the maximum time it would take will be O(n^2).
Without memoization, the time complexity would be exponential.
This is a 2D matrix that’s why the time complexity is O(n^2)
Am I correct ?
Yes you are correct.
In DP complexity can be estimated by finding the total time to fill all the DP states. Which is N^2 in this case
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.