Существует 2 вида подхода dp: сверху вниз и снизу вверх
Внизу вверх вы заполняете корпуса терминалов в таблице dp, а затем используете циклы for для построения из этого.Давайте рассмотрим восходящий алгоритм для генерации последовательности Фибоначчи.Мы устанавливаем dp[0] = 1 и dp[1] = 1 и запускаем цикл for из i = 2 to n.
. При подходе сверху вниз мы начинаем с "верхнего" взгляда на проблему и спускаемся оттуда.Рассмотрим рекурсивную функцию для получения n-го числа Фибоначчи:
def fib(n):
if n <= 1:
return 1
if dp[n] != -1:
return dp[n]
dp[n] = fib(n - 1) + fib(n - 2)
return dp[n]
Здесь мы не заполняем полную таблицу, а только случаи, с которыми мы сталкиваемся.
Почему я говорю об этих двух типах, потому что, когда вы начинаете изучать дп, часто бывает трудно придумать подходы снизу вверх (как вы пытаетесь).Когда это происходит, сначала вы хотите придумать нисходящий подход, а затем попытаться получить из этого восходящее решение.
Итак, давайте сначала создадим рекурсивную функцию dp:
# let m be size of A
# initialize dp table with all values -1
def solve(i, j, k, n, m):
# first write terminal cases
if k > A[j]:
# this means sequence is invalid. so return 0
return 0
if i >= n:
# this means a valid sequence.
return 1
if dp[i][j][k] != -1:
return dp[i][j][k]
result = 0
for num = 1 to m:
if num == j:
result += solve(i + 1, num, k + 1, n)
else:
result += solve(i + 1, num, 1, n)
dp[i][j][k] = result
return dp[i][j][k]
Итак, мы знаем, что такое терминальные случаи.Мы создаем таблицу dp размером dp [n + 1] [m] [50].Инициализируйте его всеми значениями 0, а не -1.
Таким образом, мы можем сделать восходящее как:
# initially all values in table are zero. With loop below, we set the valid endings as 1.
# So any state trying to reach valid terminal states will get 1, but invalid states will
# return the values 0
for num = 1 to m:
for occour = 1 to A[num]:
dp[n][num][occour] = 1
# now to build up from bottom, we start by filling n-1 th position
for i = n-1 to 1:
for num = 1 to m:
for occour = 1 to A[num]:
for next_num = 1 to m:
if next_num != num:
dp[i][num][occour] += dp[i + 1][next_num][1]
else:
dp[i][num][occour] += dp[i + 1][num][occour + 1]
Ответ будет:
sum = 0
for num = 1 to m:
sum += dp[1][num][1]
IЯ уверен, что должно быть какое-то более элегантное решение дп, но я верю, что это отвечает на ваш вопрос.Обратите внимание, что я считал, что k - это количество раз, которое j-е число повторялось последовательно, исправьте меня, если я ошибаюсь.
Редактировать:
С учетом ограничений размертаблица в худшем случае будет 10 ^ 5 * 6 * 50 = 3e7.Это будет> 100 МБ.Это работоспособно, но может считаться слишком большим использованием пространства (я думаю, что некоторые ядра не позволяют так много места в стеке процессу).Один из способов уменьшить это - использовать hash-map вместо массива с подходом сверху вниз, так как сверху вниз не посещает все состояния.В этом случае это будет в основном верно, например, если A [1] равен 2, то все остальные состояния, в которых 1 произошло более двух раз, не должны сохраняться.Конечно, это не сэкономит много места, если A [i] имеет большие значения, скажем, [50, 50, 50, 50, 50, 50].Другим подходом было бы немного изменить наш подход.На самом деле нам не нужно хранить размерность k, то есть времена j появлялись последовательно:
dp[i][j] = no of ways from i-th position if (i - 1)th position didn't have j and i-th position is j.
Затем нам нужно изменить наш алгоритм так:
def solve(i, j):
if i == n:
return 1
if i > n:
return 0
if dp[i][j] != -1
return dp[i][j]
result = 0
# we will first try 1 consecutive j, then 2 consecutive j's then 3 and so on
for count = 1 to A[j]:
for num = 1 to m:
if num != j:
result += solve(i + count, num)
dp[i][j] = result
return dp[i][j]
Этот подход уменьшит нашу пространственную сложность до O (10 ^ 6) ~ = 2 Мб, а временная сложность останется прежней: O (N * 6 * 50)