Flipping Burnt Pancakes, but Optimally!

This is based on the Burnt Pancake problem.

In the burnt pancake problem, each “pancake” has a burnt side. You must sort these pancakes in order with the burnt side down. You may only use one tool, your spatula, which can flip the pancakes from the top of the pancake stack to where you inserted the spatula.

Flipping pancakes that have the burnt side down results in those pancakes being in reverse order and having the burnt side up, and vice versa.

For a given array, determine the minimal number of flips needed to be made burnt pancake sorting.

Note that this is an NP-HARD problem. You may not make an approximation algorithm.

Testcases

[1,2,3,4,5] returns 0,
[3,2,1,4,5] returns (probably 10, need to verify)
[9,3,1] returns (probably 6, need to verify)

This is fastest-algorithm, so the minimal time complexity wins.