Question Link In this problem, I initially implemented a DP solution by defining the state and transition. However, it resulted in a "Memory Limit Exceeded" error. Surprisingly, when I simply interchanged the row and column while keeping the logic, states, and transitions the same, the solution was accepted.
Can someone explain why this happened?
You can see the Accepted Submission
The reason is that vector needs to store some extra information, so just a vector without elements takes some memory.
The exact memory usage of an empty vector is implementation-dependent, but usually it's 24 bytes (64bit compiler, 3 pointers)
So for your AC solution we have around
((n + 1) * 8 + 24) * 2 + 24 = 160000088bytes and for MLE solution around(2 * 8 + 24) * (n + 1) + 24 = 400000064which is 2.5 times morewell explained bro . by the way ilove_sundarKanya this question is desgined to implement space optimized solution , give it a try .