[LC] 2787. Ways to Express an Integer as Sum of Powers

[seungriyou]

https://leetcode.com/problems/ways-to-express-an-integer-as-sum-of-powers/ similar to #71

Approach

0/1 knapsack 문제이다.

Idea 1: 2D DP

• dp table을 다음과 같이 설계할 수 있다.

  dp[i][j]: 1^x ~ i^x 숫자로 이루어진 조합 중, 합쳐서 j가 되는 조합의 개수

  • 이때, i 값으로는 최대 int(n ** (1.0 / x)) + 1(즉, x 제곱해서 n이 되는 수를 올림한 값)까지만 확인하면 되므로, 그 최댓값을 max_num으로 지정한다.
  • dp table의 크기는 (max_num + 1) * (n + 1)이 된다.

• dp table을 채우는 로직은 다음과 같다.

  for i in range(max_num + 1):        # -- 물건 (~ i^x)
    dp[i][0] = 1
    for j in range(1, n + 1):       # -- 용량 (~ n)
        if j >= (val := i ** x):
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - val]) % mod
        else:
            dp[i][j] = dp[i - 1][j]

Idea 2: 1D DP

2D DP 풀이과정을 보면, dp[i - 1][j], dp[i - 1][j - val]만 사용하는 것을 알 수 있다. 따라서 1D DP로 space optimize가 가능하다.

while 문 순회를 통해 row(i)를 없애고, j >= i ** x인 범위에서 거꾸로 j를 순회하면서 dp table을 채워나간다.

# dp[j]: 1^x ~ i^x 숫자로 이루어진 조합 중, 합쳐서 j가 되는 조합의 개수
dp = [0] * (n + 1)
dp[0] = 1

i = 1
while (val := i ** x) <= n:
    for j in range(n, val - 1, -1):
        dp[j] = (dp[j] + dp[j - val]) % mod
    i += 1

Complexity

• Time: O(max_num * n)
• Space: (2D DP) O(max_num * n) / (1D DP) O(n)