Есть поле из клеток, размеры которого [n * m]. Необходимо покрыть это поле плитками размера [1 * 2] (их можно поворачивать) таким образом, чтоб все клетки поля были накрыты, и чтоб плитки не вылазили за границы поля. Задача состоит в том, чтоб найти количество таких покрытий.
Данную задачу я решил с помощью динамики по профилю. Профиль - состояние одного столбца поля. Подразумевается, что слева от данного профиля уже все клетки заполнены, а справа ещё нет. Переход из профиля в профиль существует, если можно корректно положить некоторое количество плиток (переходы хранятся в матрице dp).
Затем я считаю матрицу ответов:
if (dp[j][i]) ans[k][i] += ans[k - 1][j];
И после посчитанной матрицы ответов считаю ответ на задачу
if (isFinishing(i)) res += ans[m - 1][i];
Эта строчка означает, что если профиль может являться завершающим, то добавить это число в ответу.
Данное решение вполне себе работает. Но затем я нашел модификацию данной задачи. Модификация состоит в том, чтобы найти количество таких покрытий, в которых не будет сплошных линий из плиток [1 * 2].
Первая картинка - это пример того, какими должны быть покрытия, вторая - какими не должны.
У меня был вариант хранить в динамике ещё состояние для каждой строки, была ли она перекрыта хоть раз вертикальной плиткой, и добавлять к ответу только эти варианты. Возможно, это бы и работало, но я не особо понимаю, как это реализовать.
Подскажите, как реализовать, или предложите свои варианты решения.