Think dynamic programming


#1

The dynamic programming approach also works of complexity O(n^2)


#2

Take this question as combinatorics question. It will reduce the space as well as time complexity.