The definition of optimal substructure in the article isn’t quite right.

A problem can have optimal substructure even if merging two optimal solutions to two sub-problems that compose to form the complete problem does not provide an optimal solution to the complete problem. This happens when there is more than one way of splitting the complete problem into two sub-problems.

For example, the shortest path problem on a DAG has optimal substructure, but if you pick two subproblems by splitting the path at an intermediate node that does not lie on the shortest path, then you will not find an optimal solution by combining these.

When this happens, one needs to optimise over all the possible ways of splitting into sub-problems. This is the basis of dynamic programming.

Or graphically, this sounds like the spring paradox: https://www.youtube.com/watch?v=Cg73j3QYRJc

Sure, but the article doesn't define optimal substructure, nor does it give a general statement about it. It just talks about a specific implication that _would be_ true if code size had optimal substructure as I thought (but based on my comment above, it seems I proved myself wrong).

> Now, let's say you split the function in two parts and you find their minimums independently. Optimal substructure tells us that if you just merge these two, you'll get the minimum version of the whole function.

Optimal substructure doesn't tell us this. I don't know whether or not this problem has optimal substructure, but even if it did, it still wouldn't tell us this.

Optimal substructure means it is possible to construct an optimal solution from optimal solutions to its subproblems; it doesn't mean that optimal solutions to arbitrary pair of subproblems (that compose to form the complete problem) can be used to form an optimal solution, which is what I understood the quoted section of the article to be saying.

Thanks, it looks like I had forgotten how dynamic programming works, e.g. constructing from possibly all subproblem solutions rather than just some way of breaking into some disjoint union. In this case I guess for code optimization a "subproblem" needs to be defined. I'm not sure if just breaking the code into chunks works as I was imagining. Maybe optimal substructure applies to some graph-like model of computation but not the naive assumption I made on how this would work.

Yes I was surprised at that sentence because I think (considering theoretical properties of code size are the same as instruction count) that the main initial reason compiler optimization is non-trivial is because these kinds of global optimizations are possible, like your loop example.

Also I am really enjoying your article, still reading it with wikipedia open on the side haha.

Nice to hear that! I hope nothing else is questionable. And thanks for pointing it out! I guess the moral of the story is don't do "proofs" in your head after 3am.