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

# DP_solution in O(n^3) time complexity

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.