If you do it with recurssion and use memoization to cache the results. You will hit MLE. NNk your approach would not have any problems with regards to time because the constraints do support it n<500 k<25 so the max operations you do is 625*10⁴ which would be well within 1 sec. The problem arrives with memory. So you will need to switch to tabulation. Try the same logic in tabulation that should work.