DP_solution in O(n^3) time complexity


Just think in terms of MATRIX MULTIPLICATION DP.You will get the answer.


NO, it gives only tle.


There is also a O(n^2) solution, but that doesn’t satisfy always. So I opted for correct method which is O(n^3) time complexity and it ran correctly both here and on Leetcode.


Times out 1 test case on leetcode. Maybe u used c++, I cant use that ,sorry.
Edit : It tles even in c++. I need to learn the N^2 solution.