[Python] Struggling with bottom up approach for This Kattis Problem: The mailbox manufacturers

Problem link : https://open.kattis.com/problems/mailbox

It feels like a variation of Egg dropping problem but i cant seem to wrap my head around how I am unable to do this. It is also tagged as an easy problem: This is what I have so far:

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[j] = float('inf')
for x in range(1, j + 1):
dp[j] = min(dp[j], x + max(dp[i - 1][x - 1], dp[j - x]))

print(dp[k][m])


I was able to get a C++ code that uses 3D matrix to solve it bottom up using this recurrence :

dp\[i\]\[low\]\[high\]=min(max(dp\[i−1\]\[low\]\[mid−1\],dp\[i\]\[mid\]\[high\])+mid)


but that uses up a lot of space and i was wondering whether it could be done in 2D?

Continue reading...