Why does recursion + memoization solution gives TLE ?
Link to Submission
U can use simple 2 nested loops & a 1-D array for the problem .
here is my sol.- CodeChef: Practical coding for everyone
can you explain your approach ?
have u seen that apparoch?
I think its always better to stay away from recursive dp whenever possible due to the difficulty in calculating time complexity and if you make 1 small mistake it might lead to TLE or WA.
My iterative dp solution: CodeChef: Practical coding for everyone
The basic idea is-
length(k) 1 2 3 4 5
n
1-> 1 1 1 1 1
2-> 2 3 4 5 6 (5+1)
3-> 3 6 10 15 21 (6+15)
4-> 4 10 20 35 56 (21+35) (a[n][k]=a[n-1][k]+a[n][k-1])
I think u can easily understand what pattern it is following.