> And how do you find "subproblems that might potentially overlap"? You go through the space and cache results of your calculations.
I addressed this directly in my comment? At the risk of repeating it: you don't have to even think about caching anything in order to find "subproblems that might potentially overlap". The example I gave directly in my comment illustrated this vividly: the shortest N-hop path from A to B is the shortest of all (N-1)-hop paths after all the first hops you can possibly traverse from A. Is it clear what the subproblems are? Yes, they're the (N-1)-hop subproblems. Is it clear why they might overlap? Yes, because after a couple hops you might end up in the same location. Was caching relevant to understanding the aforementioned? No, it didn't even need to cross your mind - the point was the problem decomposition. Caching is just a generic optimization you can apply later to DP, just like you can to divide-and-conquer (and to other stuff).
I addressed this directly in my comment? At the risk of repeating it: you don't have to even think about caching anything in order to find "subproblems that might potentially overlap". The example I gave directly in my comment illustrated this vividly: the shortest N-hop path from A to B is the shortest of all (N-1)-hop paths after all the first hops you can possibly traverse from A. Is it clear what the subproblems are? Yes, they're the (N-1)-hop subproblems. Is it clear why they might overlap? Yes, because after a couple hops you might end up in the same location. Was caching relevant to understanding the aforementioned? No, it didn't even need to cross your mind - the point was the problem decomposition. Caching is just a generic optimization you can apply later to DP, just like you can to divide-and-conquer (and to other stuff).