[PYTHON] Atcoder ABC099 C - Solution séparée de Strange Bank

AtcoderProblem est assez difficile dans la seconde moitié du niveau de difficulté vert, mais il semble y avoir différentes solutions ...

Récursif

saiki.py

# coding: utf-8
# Your code here!
N=int(input())

def saiki(tgt,i,count,ans):
    #print(tgt,i,count,ans,temp[i])

    if i==0 or tgt==0:
        ans=min((tgt+count),ans)
        return ans
        
    num=tgt//temp[i]
    while num>=0:
        ans=saiki(tgt-num*temp[i],i-1,count+num,ans)
        if ans<(count+num):
            return ans
        num-=1
    return ans

temp=[1]
n=1
while N>=6**n:
    temp.append(6**n)
    n+=1
    
n=1
while N>=9**n:
    temp.append(9**n)
    n+=1

temp.sort()

print(saiki(N,len(temp)-1,0,10**9))

Je l'ai fait quand il était brun, donc c'est un peu en désordre. Je n'aime pas les récurrences parce que j'écris des boucles infinies

Méthode de planification dynamique

dynamic.py

# coding: utf-8
# Your code here!
N=int(input())

lis=[]

temp=6
while temp<=N:
    lis.append(temp)
    temp*=6

temp=9
while temp<=N:
    lis.append(temp)
    temp*=9

lis.sort(reverse=True)

dp=[10**9]*(N+1)
dp[0]=0

#Tableau dp[N+1]Notez le nombre minimum d'étapes pour créer le numéro d'index
for item in lis:
    for i in range(N+1):
        if dp[i]!=10**9:
            if i+item<=N:
                dp[i+item]=min(dp[i]+1,dp[i+item])
            
ans=10**10
for index,item in enumerate(dp):
    ans=min(ans,item+N-index)
print(ans)

Je pensais que c'était plus facile et plus simple

J'étais conscient de la solution du sac à dos Comme je l'ai remarqué plus tard, si vous commencez à écrire en dp comme cette fois à partir de 1, ce sera un nombre infini de sacs à dos, et si vous partez du contraire, ce sera un nombre limité de sacs à dos.

bfs Je ne sais pas Je le ferai un jour