recursive dp is slower bc you make recursive calls and calling a function is slow

Recursive implementations of DP questions almost always takes more time because of the function calls and the recursive call stack.

That's why high rated folks always prefer iterative DP because it can run in tighter constraints and also for the fact that many optimization techniques are only possible in the iterative versions (like taking prefix sums of previously computed rows or running range queries on them).

recursive dp quite slower comparatively but for this problem my recursive dp solution ran below 400ms 268191223

People say it's slower because of recursion but it's not just that, I think that's actually a small part of it. The main 2 differences (according to my intuition) are:

1. When you do memoization+recursion then your code ends up having a lot more ifs. Read https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array I've read this answer in 2015-2016 and it's very enlightening.

2. You visit memory in an unorderly manner, causing more cache misses. https://mirror.codeforces.com/contest/1987/submission/281498628 this is your recursive code but with fors calling the DP in a good order, forcing it to use memory in a less random order and execution time was cut to 800ms.