In my code I am using recursion. If i used "long long ret=dp[l][r];" It gave TLE


#1

In my code I am using recursion.
If i used "long long ret=dp[l][r];"
It gave TLE error.
But when I changed it too “long long &ret=dp[l][r];” without changing anything else it worked well.
Why is that so?


#2

In latter case ret is a reference to dp[l][r], so any update in value of ret will be like updating value of dp[l][r]. In memoisation, we don’t recalculate values we’ve already calculated. But if you use the former statement, you are not actually storing the values which you’ve calculated anywhere, you just return it from the function. Hence, there is no memoisation, which leads to TLE.