Я пытался решить эту проблему с помощью Dynami c Programming, но, похоже, мне не хватает некоторых случаев, которые я не могу найти.
Вот уравнение, которое я использовал для получения значений из подзадачи
dp[i][j] = dp[i][j-1] + 3*(dp[i-1][j-1] - dp[i-2][j-2]) + dp[i-3][j-2]
(i = k = количество окрашиваемых ячеек и j = n = количество столбцов, обратите внимание, что строка является фиксированной, т.е. 3)
термины определены ниже:
dp[i][j-1]: случай, когда я не окрашиваю ни одну ячейку в n-м столбце.
dp[i-1][j-1] - dp[i-2][j-2]: случай, когда я окрашиваю одну ячейку в последнем столбце а затем вычтите случай, когда я окрашиваю соседнюю ячейку в столбце n-1, и, поскольку это можно сделать для каждой из 3 ячеек в столбце n, я умножил это на 3.
dp[i-3][j-2] : случай, когда я раскрашиваю две ячейки (верхнюю и нижнюю) в n-м столбце и, таким образом, имею только один выбор для n-1-го столбца, это средний, следовательно, вычитая 3 из i , и поскольку мы уже рассмотрел последние два столбца Я уменьшаю 2 с j .
* 1 024 * Я не смог найти ни одной ошибки в вышеупомянутом подходе. Если вы заметили какую-либо ошибку, пожалуйста, помогите.
Ниже приведен фактический вопрос, в котором также упоминается дополнительное условие для столбца P, который не должен быть пустым, и должен быть
Мой подход состоит в том, чтобы сначала найти все возможные способы раскрасить k ячеек в матрице 3xN таким образом, чтобы они не были смежными, а затем найти количество способов, в которых существуют P последовательных столбцов, так что не существует ячейки, окрашенные в них, и вычитая его из общего количества, но в этом подходе мне не хватает правильного ответа с небольшим запасом для меньших входных данных и большим запасом для больших входных данных. Мне здесь чего-то не хватает.
