Find min cost of painting houses

Задача: в ряд стоят N домов, каждый из которых должен быть покрашен в один из 3х цветов: красный, синий или зеленый.

• Однако стоимость покраски каждого дома в определенный цвет разная.
• Также необходимо покрасить дома так, чтобы никакие два соседних дома не были одного цвета.

Посчитайте минимальную стоимость покраски всех домов.

Входные данные: cost[i][j] — массив массивов Nx3, где стоимость окраски i-го дома в красный цвет равна cost[i][0], в синий — cost[i][1], в зеленый — cost[i][2].

1 <= N <= 100.

Вывод: минимальная стоимость покраски всех домов.

Пример:

[17,2,17],

[16,16,5],

[14,3,19]

Output: 10 (1й дом красим в синий (2) + 2й дом красим в зеленый (5) + 3й дом снова красим в синий (3))

Разбор

Рассмотрим эту задачу для i-го дома. Мы уже покрасили (i — 1) дом, и теперь у нас есть 3 варианта:

• покрасить в красный
• покрасить в зеленый
• покрасить в синий.

Тогда получаем следующую реккурентную формулу: если мы решим покрасить i-й дом в красный цвет, то затраты будут: