Задача про стену и кирпичи. Как решить? Добрый день!
Задали на юниорском собеседовании такую задачу, на которой я застрял.
Вот задача, подскажите куда копать? Все решение которые мне в голову приходят требуют огромного количества памяти и жутко неоптимальны:(
Сама задача:
Есть два вида кирпичей: длиной 3 и 4. Из этих кирпичей нужно построить стену длиной 25 и высотой 10 рядов. Дополнительное условие - в двух последовательных рядах щели между кирпичами не должны создавать вертикальные линии. То есть, к примеру стену длиной 8 и высотой в два ряда не построить(1 ряд (4,4), 2 ряд (4,4) - щель по середине).
Требуется посчитать, сколько всего возможных комбинаций кирпичей при постройке стены такого размера.
Заранее спасибо за помощь

Предыдущий
вопрос Следующий
вопрос

Привет! Для решения данной задачи можно воспользоваться динамическим программированием.

Давайте создадим массив dp, где dp[i] будет обозначать количество способов построить стену высотой i.

Изначально dp[0] = 1 (если стена нулевой высоты, то способов построить ее всего один - ничего не делать).

Далее, для каждой высоты i (от 1 до 10) будем перебирать возможные способы построить стену. С каждым кирпичом добавляемым к текущей стене, будем обновлять значение dp[i] суммируя dp[i-3] (если добавляем кирпич длиной 3) и dp[i-4] (если добавляем кирпич длиной 4).

В конце алгоритма, dp[10] будет содержать искомое количество способов построить стену высотой 10.

Таким образом, необходимо написать код на Python, который решит данную задачу. Ниже привожу пример такого решения:

def count_ways_to_build_wall(height):
dp = [0] * (height + 1)
dp[0] = 1
for i in range(1, height + 1):
if i >= 3:
dp[i] += dp[i-3]
if i >= 4:
dp[i] += dp[i-4]
return dp[height]
total_ways = count_ways_to_build_wall(10)
print(total_ways)

Этот код подсчитает количество возможных способов построить стену высотой 10 рядов при условиях задачи. Надеюсь, это поможет вам продвинуться к решению задачи :)