Шахматную доску ???? × ???? нужно разрезать на ????·???? единичных квадратов.

Минимальная стоимость (n-1)*m+(m-1)*n. Вы можете получить, сделав m горизонтальных разреза, заплатив за каждый n-1 и n вертикальный разрез, заплатив за каждый m-1. Это алгоритм O(1).

Чтобы отрезать единичный квадрат, нужно заплатить за него минимум 2 в (n-1)*(m-1) случаях, минимум 1 в (n-1)+(m-1), а один единичный квадрат можно получить бесплатно. Это ограничивает общую цену снизу:

2*(n-1)*(m-1)+1*(n-1)+(m-1)+0*1 = 2*n*m-n-m = (n-1)*m+(m-1)*n

Вот подход к динамическому программированию, который работает в O (m * n * (m + n)).

Для каждого возможного размера w * h подпрямоугольника вычислите стоимость f (w, h) его разрезания на отдельные квадраты. Выберите первый разрез: w * h разрезается либо на a * h и b * h, либо на w * c и w * d. Стоимость разрезания на a * h и b * h составляет min (a, b) * h + f (a, h) + f (b, h). Стоимость разрезания на w * c и w * d составляет w * min (c, d) + f (w, c) + f (w, d). Собрав все это вместе, мы имеем

f (w, h) = min of
                min {for every a such that 0 < a < w}
                    (let b = w - a)
                    min (a, b) * h + f (a, h) + f (b, h)
           and
                min {for every c such that 0 < c < h}
                    (let d = h - c)
                    w * min (c, d) + f (w, c) + f (w, d)

База f (1, 1) = 0.

Мы можем хранить все f (w, h) в виде двумерного массива и вычислять их снизу вверх в двух циклах, например так:

for w = 1, 2, ..., m:
    for h = 1, 2, ..., n:
        calculate f[w][h] by the formula above in O (w + h)

Или напишите рекурсивную функцию с мемоизацией.

Любой из двух подходов будет работать в O (m * n * (m + n)): мы должны вычислить m * n значений, и каждое вычисляется как минимум O (m + n) значений.

Если жадный подход действительно работает (я не знаю), он будет делать это за O (log m + log n). По интуитивному рассуждению, например, если m = 17 и n = 23, то должны рассматриваться следующие прямоугольники:

17 * 23
17 * 11 and 17 * 12
 8 * 11 and  8 * 12 and  9 * 11 and  9 * 12
 8 *  5 and  8 *  6 and  9 *  5 and  9 *  6
 4 *  5 and  4 *  6 and  5 *  5 and  5 *  6
 4 *  2 and  4 *  3 and  5 *  2 and  5 *  3
 2 *  2 and  2 *  3 and  3 *  2 and  3 *  3
 1 *  1 and  1 *  2 and  2 *  1 and  2 *  2
 1 *  1 again

Как мы видим, прямоугольники будут иметь форму (m / 2^x) * (n / 2^y), где x и y находятся между 0 и log_2 (m + n), и округление может идти в любую сторону.