ABC099C - Strange Bank

きっかけ：ABC219Dと次の記事．
貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita

DP

考え方

答えを$f(N)$とすると，$x = 0,1,...,N-1$に対して$f(x)$がわかっていれば$f(N)$が計算できる．よって，DPで求められる．

具体的には，

\begin{aligned}
f(N)
=\min \{ f(N - 1) + 1, f(N - 6^{i}) + 1, f(N - 9^{i}) + 1 \}
\end{aligned}

である（ただし，$i$は可能な範囲をすべて動く）．

以下，$f(i)$をdp[i]で表す．

貰うDP

dp[i]に遷移させるように更新する．

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(1, N + 1):
  for j in [6, 9]:
    k = j
    while k <= i:
      dp[i] = min(dp[i], dp[i - k] + 1)
      k *= j
  dp[i] = min(dp[i], dp[i - 1] + 1)
      
print(dp[N])

配るDP

dp[i]から遷移するように更新する．

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
  for j in [6, 9]:
    k = j
    while i + k <= N:
      dp[i + k] = min(dp[i + k], dp[i] + 1)
      k *= j
  if i + 1 <= N:
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
      
print(dp[N])

メモ化再帰

from functools import lru_cache
N = int(input())

@lru_cache(maxsize = None)
def f(x):
  if x == 0:
    return 0
  p, q = 1, 1
  while x - 9 ** p >= 0:
    p += 1
  while x - 6 ** q >= 0:
    q += 1
  tmp1 = f(x - 9 ** (p - 1)) + 1
  tmp2 = f(x - 6 ** (q - 1)) + 1
  return min(tmp1, tmp2)

print(f(N))