When a recursive algorithm solves the same smaller problem multiple times, I call these overlapping subproblems. This concept is new for most people the first time. If it feels abstract right now, you're in good company.
In your Fibonacci tree, appears twice, appears three times. These are overlapping subproblems. Contrast this with merge sort, where each recursive call works on a different portion of the array (no overlap). Overlapping subproblems are a strong sign that DP can help.
This is the #1 reason DP (DP) solutions time out. What If could the answer to the first time? You wouldn't need to recalculate it, right? .
