389. What goes wrong when a problem does not have optimal substructure? Give an example.
HardDynamic programming
Show model answer
DP assumes an optimal solution is built from optimal solutions to independent subproblems. Longest simple path breaks this: if the longest path from u to w passes through v, the u→v part need not be a longest u→v path, and combining two longest subpaths can reuse a vertex, giving an invalid path. The subproblems interact, so any table of 'best answers' is wrong. Longest simple path is NP-hard in general graphs (but solvable in O(V + E) on DAGs, where no vertex can repeat).
Shortest paths do have optimal substructure (when there are no negative cycles), which is why Bellman–Ford and Dijkstra work. When a recurrence seems to fail, often the fix is a richer state, for example adding the set of visited vertices (Held–Karp for TSP, O(2ⁿ · n²)) or adding 'number of transactions left' in stock problems.