Notice that the above solution takes formula_88 time with a DP solution. This can be improved to formula_89 time by binary searching on the optimal formula_90 in the above recurrence, since formula_91 is increasing in formula_90 while formula_93 is decreasing in formula_90, thus a local minimum of formula_95 is a global minimum. Also, by storing the optimal formula_90 for each cell in the DP table and referring to its value for the previous cell, the optimal formula_90 for each cell can be found in constant time, improving it to formula_98 time. However, there is an even faster solution that involves a different parametrization of the problem: