Python 競プロで動的計画法を使ったのですが..

Pythonでatcoderの問題を解いていて、動的計画法を使ったのですが、最初の方はACなのですが最後の方がWAになってしまいます。

以下、僕の書いたソースコードです。

Python
1
2n=int(input())
3dp=[float("inf")]*n
4dp[0]=1
5for i in range(n-1):
6    for j in range(1,7):
7        j=6**j
8        if i+j<n:
9            dp[i+j]=min(dp[i+j],dp[i]+1)
10    for j in range(1,6):
11        j=9**j
12        if i+j<n:
13            dp[i+j]=min(dp[i+j],dp[i]+1)
14    dp[i+1]=min(dp[i+1],dp[i]+1)
15    
16
17print(dp[-1])
18

与えられるNが10^5未満なので、6のべき乗は6乗まで、9は5乗までにしてforループを回しました。どこが間違っているのかわかりません...教えて頂きたいです。よろしくお願い致します。

行動規範の内容に同意します

回答1件

ベストアンサー

dp[i]をi+1円引き出すのに必要な最小回数としていますが、
dp[i]をi円引き出すのに必要な最小回数したほうが良いかと思います。

py
1n=int(input())
2dp=[float("inf")]*(n+1)
3dp[0]=0
4for i in range(n):
5    for j in range(1,7):
6        j=6**j
7        if i+j<=n:
8            dp[i+j]=min(dp[i+j],dp[i]+1)
9    for j in range(1,6):
10        j=9**j
11        if i+j<=n:
12            dp[i+j]=min(dp[i+j],dp[i]+1)
13    dp[i+1]=min(dp[i+1],dp[i]+1)
14
15
16print(dp[-1])