Would you mind pinpointing where exactly you feel I would lose students in the above approach? Would I lose people at the mention of "DAG"? in which case... isn't it easy enough to jog their memory in a few seconds ("it's like a tree, except a node can have multiple parents" <drawing>) if they've forgotten what that is? Or is it with the N-hop example? In which case, aren't there plenty of simpler ones (like Fibonacci) you can use instead? Or do you see somewhere else where people would get overwhelmed, and if so, where?

Like, I would understand where you're coming from if I'd used the pumping lemma or something like you're imagining, but that's not what's happening here? All I did was merely mention the words "subproblems", "trees", and "DAGs"... that's it. No theorems, no proofs, not even any need to remember what caching is... just descriptions with vivid examples and diagrams. All of which you can re-explain in a few minutes if they've forgotten them. I have a hard time seeing why that should scare someone away who's otherwise in a position to learn DP.

Also, isn't the audience kinda important here? It's not like this was intended for 10-year-olds like New Math. It was intended for college-level CS students and above. They can and should be expected to have a greater understanding (and attention span) than elementary school students.