Борьба с подходом внизу вверх для этой проблемы Каттиса: производители почтовых ящиков ⇐ Python

[Anonymous]

Описание задачи:
Производитель почтового ящика хочет протестировать долговечность нового почтового ящика в зависимости от того, сколько пожарных крекеров он может выдержать. Учитывая k идентичные почтовые ящики (каждая из которых удерживает до M Crackers), найдите минимальное количество фейерверков, необходимых для определения максимальных крекеров, которые можно выдержать почтовый ящик без взрыва. x - 1. В противном случае его можно использовать повторно. https://open.kattis.com/problems/mailbox

Это похоже на изменение проблемы с отбросом яйца, но я не могу обернуть голову вокруг того, как я не могу это сделать. Это также помечено как простая проблема:
Это то, что у меня есть до сих пор: < /p>

Код: Выделить всё

import sys

t = int(input().strip())

for _ in range(t):
k, m = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(k + 1)]

for j in range(1, m + 1):
dp[1][j] = (j * (j + 1)) // 2

for i in range(2, k + 1):
for j in range(1, m + 1):
dp[i][j] = float('inf')
for x in range(1, j + 1):
dp[i][j] = min(dp[i][j], x + max(dp[i - 1][x - 1], dp[i][j - x]))

print(dp[k][m])
< /code>
Я смог получить код C ++, который использует 3D-матрицу, чтобы решить его снизу вверх, используя этот рецидив: < /p>
dp\[i\]\[low\]\[high\]=min​(max(dp\[i−1\]\[low\]\[mid−1\],dp\[i\]\[mid\]\[high\])+mid)

Но это использует много места, и мне было интересно, можно ли это сделать в 2D?


Подробнее здесь: https://stackoverflow.com/questions/794 ... x-manufact