Editorial is given of Dynamic programming

#1

Sir the editorial is given of this problem is of Dynamic programming, can you give a recursive solution. My solution is passing a test case and failing other because of TLE. I think this is because time limit is set not for 2^n but to o(n).

This is my code and its giving correct output as per i checked.

https://ideone.com/e.js/j9zS3N

#2

for big input your code will run into TLE and stackoverflow.
so try to build answer using array and use bottom up approach.