Python: понимание решения Stairstep DP
Я смотрел на эту проблему.
- Цель состоит в том, чтобы построить лестницы из кирпича
- Есть N кирпичей, и все они должны быть использованы для строительства лестницы
- Лестницы состоят из ступеней разных размеров в строго возрастающем порядке
- Лестница не имеет ступеней одинакового размера.
- Каждая лестница состоит как минимум из двух ступеней, а каждая ступенька содержит как минимум один кирпич
Ссылка на полную проблему http://acm.timus.ru/problem.aspx?num=1017&locale=en
Я уже знаю, что это имеет дело с различными разделами и теорией чисел / проблемой ранца. Целью фактически является список n = [1,2,3,....n -1], определяющий, сколько неупорядоченных множеств, которые складываются в N, существуют. Я говорю неупорядоченный, потому что в списке нет дубликатов, поэтому любая комбинация может быть отсортирована как правильный конкретный ответ на заданный размер, чтобы соответствовать правилам. Я также понимаю, что общая концепция заключается в том, что вы начинаете с высоты 1 и ветвитесь / добавляете все возможные комбинации, продолжая, пока новая высота не переходит на кирпичи, и только добавляя к общим комбинациям, если новая высота использует все оставшиеся кирпичи в этот момент. Я понимаю, что существуют такие шаблоны, как вы уже знаете, сколько разделов существует для n = 3, когда переходите к 4, поэтому использование этих данных (динамическое программирование) является частью решения.
В итоге я наткнулся на следующее решение.
n = int(input())
m = [[0 for i in range(n + 1)] for j in range(n + 1)]
m[0][0] = 1 # base case
for last in range(1, n + 1):
for left in range(0, n + 1):
m[last][left] = m[last - 1][left]
if left >= last:
m[last][left] += m[last - 1][left - last]
print(m[n][n] - 1)
Итак, я понимаю, что последняя переменная показывает, сколько кирпичей она использует. И левый цикл перебирает и передает кэшированные данные. Таким образом, я понимаю, что m[last][left] назначается входу, потому что он уже имеет вычисленную сумму разбиения для всех возможных ступеней, использующих кирпичи last - 1.
Я также получаю, что диагональ содержит все числа разделов ( [3,3] = различные разделы кирпичей = 3) Часть, в которой я не уверен, - это способ определения данных после проверки диагонали (если оставлено>= последний) Как алгоритм узнает, что при добавлении этого точного местоположения матрицы к текущему индексу получаются правильные значения? Какова связь между данными в этих точках.
Ниже приведена матрица 2d массива после запуска на 10, где ответ 9
= 0 1 2 3 4 5 6 7 8 9 10
0 | 1 0 0 0 0 0 0 0 0 0 0 0
1 | 1 1 0 0 0 0 0 0 0 0 0
2 | 1 1 1 1 0 0 0 0 0 0 0 0
3 | 1 1 1 2 1 1 1 0 0 0 0
4 | 1 1 1 2 2 2 2 2 1 1 1
5 | 1 1 1 2 2 3 3 3 3 3 3
6 | 1 1 1 2 2 3 4 4 4 5 5
7 | 1 1 1 2 2 3 4 5 5 6 7
8 | 1 1 1 2 2 3 4 5 6 7 8
9 | 1 1 1 2 2 3 4 5 6 8 9
10 | 1 1 1 2 2 3 4 5 6 8 10
1 ответ
Интуиция, лежащая в основе восходящего решения этой проблемы, немного сложна для понимания, но здесь говорится:
Во-первых, давайте переименуем m к чему-то более интуитивному: ways, Теперь, когда мы исследуем проблему, мы видим, что в этой задаче есть конечное число состояний. Пространство состояний определяется last, который вы можете считать количеством кирпичей за последний сделанный вами шаг, и left, который является количеством кирпичей, которые вы оставили использовать.
Таким образом, ways[last][left] представляет количество лестниц, которые вы можете построить, если высшая ступень вашей лестницы имеет высоту last, и у тебя есть left кирпичи для работы.
Теперь давайте посмотрим на базовый вариант. ways[0][0] говорит нам, сколько лестниц мы можем построить, если у нас есть шаг высоты 0 и у нас осталось 0 кирпичей. Ну, есть только один способ сделать это: положить 0 кирпичей вниз! Как следствие, ways[0][0] = 1, Если вы посмотрите на ways[0][1], это спрашивает: сколько способов мы можем построить лестницу, если последний шаг был 0 высотой, и у нас остался 1 кирпич? Это невозможно, потому что высота ступеней, идущих слева направо, должна строго увеличиваться. Как вы видете, ways[0][1], ways[0][2], ... , ways[0][k], k > 0 все будет ноль.
Самая сложная часть восходящего решения - повторение. Давайте посмотрим на первую строку внутри вложенного цикла for.
ways[last][left] = ways[last - 1][left]
Это говорит о том, что количество лестниц, которые мы можем сделать за последний шаг высоты last а также left количество оставшихся кирпичей равно количеству лестниц, которые мы можем сделать за последний шаг высоты last-1 с left кирпичи остались. Это должно иметь смысл, потому что если у вас есть более высокий последний шаг, он становится менее ограничительным, и ways[last][left] становится надмножеством ways[last-1][left], Подумайте об этом так: у нас есть 5 кирпичей для работы. Сколько лестниц мы сможем сделать? То же самое число, которое мы могли бы сделать с 4 кирпичами. По крайней мере, вы можете просто добавить лишний кирпич к самому высокому шагу справа, и он все равно будет действителен.
4 bricks 5 bricks
#
# #
# #
## ##
13 14
Что происходит, когда количество оставленных вами кирпичей больше или равно количеству кирпичей на вашем последнем уровне? В этом случае мы можем построить новую лестницу слева от существующего шага. Но эта новая лестница не может быть больше, чем last-1 кирпичи высокие, потому что, опять же, шаги должны строго увеличиваться. Так сколько там лестниц? Ну, мы используем last кирпичи, чтобы сделать шаг, поэтому мы имеем left-last кирпичи, оставшиеся, чтобы создать лестницы слева. Это число в клетке ways[last-1][left-last], К счастью, мы вычислили это значение раньше, так что это просто поиск.
Пример может помочь с фактическими числами, поэтому я проведу расчет для n=2,
# initial state with the base case
[1, 0, 0]
[0, 0, 0]
[0, 0, 0]
# ways[1][0] = ways[0][0] at least b/c the spare brick can go on highest step
[1, 0, 0]
[1, 0, 0]
[0, 0, 0]
# ways[1][1] = ways[0][1] by the same logic
# ways[1][1] += ways[0][0] because we use up 1 brick making the step,
# and we have 0 bricks left, and we need the max height to be 0
[1, 0, 0]
[1, 1, 0]
[0, 0, 0]
# ways[1][2] = ways[0][2] by the same logic
# ways[1][2] += ways[0][1] because we use up 1 brick making the step,
# and we have 1 bricks left, and we need the max height to be 0 (impossible!)
[1, 0, 0]
[1, 1, 0]
[0, 0, 0]
# ways[2][0] = ways[1][0] by the same logic
[1, 0, 0]
[1, 1, 0]
[1, 0, 0]
# ways[2][1] = ways[1][1] by the same logic
# ways[2][1] += ways[1][0] because we use up 1 brick making the step,
# and we have 0 bricks left, and we need the max height to be 0
[1, 0, 0]
[1, 1, 0]
[1, 1, 0]
# ways[2][2] = ways[1][2] by the same logic
# ways[2][2] += ways[1][0] because we use up 2 bricks making the step,
# and we have 0 bricks left, and we need the max height to be 1.
# That's perfect, because we can make a step of max height 1 with 0 steps
[1, 0, 0]
[1, 1, 0]
[1, 1, 1]
Это логика заполнения ways Таблица. Это последняя строка кода:
print(ways[n][n] - 1)
Причина, по которой нам нужно вычесть 1, частично связана с нашим базовым случаем. Мы предполагаем, что есть 1 способ сделать лестницу с 0 кирпичами и 0 высотой. Однако в действительности это не является "лестницей" в соответствии с правилами, потому что лестница должна иметь два или более ступеней. Из-за этого каждая диагональная запись включает одну дополнительную "недопустимую" лестницу: n кирпичей, уложенных друг на друга.
4 bricks
#
# #
# #
## #
13 4
Нам это нужно, потому что в будущих лестницах мы могли бы использовать n кирпичи сложены друг на друга, как если бы у нас было 9 кирпичей.
9 bricks
# #
# ##
## ##
## ##
### ##
135 45
Просто когда у тебя есть только n кирпичи, вы должны вычесть этот неверный случай.
Я надеюсь, что это помогло - удачи!