Interesting.. It's somehow tough for me to accept that a "NP complete" problem can be solved with a regular language.

You construct a DFA. Your start state has (string of toy length) transitions to every possible toy. Then these toys all have self edges looping to themselves (with a string of length toy), and edges to every other toy (with those edges being the length of the other toy)...

But what is your accepting state, do you have 2 "escape" transitions of "toy cost" and "other toy cost" from "toy" to a terminating, accepting state? (Does that work?)

It feels like an abuse of regular languages and automata, and I'm not sure it works...

This is like saying: the balanced parentheses problem can be solved by a regular language, *if you fix the balanced parentheses problem to strings of 2^5 length, and build a machine that accepts all balanced parentheses combinations of 2^5 length. Like yeah, you could hack together an automata to recognize all 2^5 strings, but is it a proper automata at that point?