import functools
#PROBELM NAJMANJŠEGA ŠTEVILA KOVANCEV:
# podano imamo naravno število 'k' in množico naravnih števil, ki predstavlja 
# kovance, ki so na voljo. Zanima nas najmanjše število kovancev, ki jih moramo
# vzeti, da bo vrednost kovancev enaka podanemu številu 'k'

#Podana je rekurzivna rešitev zgornjega problema
def kovanci_rekurzija(tabela_kovancev,vsota):
    '''rekurzivna rešitev, ki vrne najmanjše število kovancev, ki jih potrebujemo, da dobimo podano vsoto '''
    if vsota == 0:
        return 0
    try:
        return 1 + min([kovanci_rekurzija(tabela_kovancev,vsota-kovanec) for kovanec in tabela_kovancev if vsota-kovanec >= 0])
    except:# takega števila ni mogoče dobiti z danim naborom kovancev
        return float('inf')
    
#ŠE Z MEMOIZACIJO
def rekurzija_kovanci(tabela,vsota): #do cca 25000
    @functools.lru_cache(maxsize=None)
    def kovanci_rekurzija_v2(vsota):
        if vsota == 0:
            return 0
        try:
            return 1 + min([kovanci_rekurzija_v2(vsota-kovanec)
                       for kovanec in tabela if vsota-kovanec >= 0])
        except:# takega števila ni mogoče dobiti z danim naborom kovancev
            return float('inf')
    return kovanci_rekurzija_v2(vsota)
    
#S pomočjo zgornje rešitve implementiraj še
#iterativno rešitev(dinamično programiranje)
#==========================================================
    
# def kovanci_dinamicna(tabela_kovancev,vsota):
#     '''dinamična metoda za iskanje najmanjšega število kovancev,
#        ki jih potrebujemo, da dobimo podano vsoto
#     '''
#     #ustvarimo tabelo
#     tabela = [float('inf')]*(vsota +1)
#     tabela[0] = 0
        
        #DOPOLNI

#     return tabela[-1]

    
#=======================================================


#PROBLEM NAJMANJŠEGA ŠTEVLA ENIC V ARITMETIČNEM IZRAZU:
# V aritmetičnem izrazu lahko uporabljamo zgolj znake oziroma števila iz
# nabora znakov {+,*,1}.Pri podanem  naravnem številu $k$ nas zanima,
# kolikšno je najmanjše število enic v aritmetičnem izrazu,
# katerega vrednost je enaka podanemu številu k.

#Podana je rekurzivna rešitev zgornjega problema
@functools.lru_cache(maxsize=None)
def stevilo_enic_rekurzija(stevilo):
    '''
        rekurzivna rešitev, ki vrne najmanjše število enic,
        ki jih potrebujemo, da z naborom znakov {+,*,(,),1}
        dobimo aritmetični izraz, katerega vrednost je enak številu 'stevilo'
    '''
    if stevilo == 1:
        return 1
    vsota = min([stevilo_enic_rekurzija(stevilo - i) + stevilo_enic_rekurzija(i) for i in range(1,int(stevilo // 2) + 1)])
    try:
        zmnozek = min([stevilo_enic_rekurzija(stevilo / i) + stevilo_enic_rekurzija(i) for  i in range(2,int(stevilo**(1/2)) +1) if stevilo / i == stevilo // i ])
    except:
        return vsota
    return min(vsota,zmnozek)


#S pomočjo zgornje rešitve implementiraj še
#iterativno rešitev(dinamično programiranje)
#==========================================================
# def stevilo_enic_dinamicna(stevilo):
#     '''
#         dinamična rešitev, ki vrne najmanjše število enic,
#         ki jih potrebujemo, da z naborom znakov {+,*,(,),1}
#         dobimo aritmetični izraz, katerega vrednost je enak številu 'stevilo'
#     '''
#     if stevilo < 1:
#         #DOPOLNI
#     tabela = [float('inf')]*(stevilo +1)
#     tabela[0] = 0
#     tabela[1] = 1
#     for st in range(2,stevilo+1):
#         #DOPOLNI
#         #POGLEDAMO PO VSOTAH IN PRODUKTIH
#         #VZAMEMO MINIMUM!
#         
#         
#         
#     return tabela[-1]

#=======================================================================0
#testni primeri:

tabela_kovancev= [1,5,6,9,15,50]
pravilno = True
for i in range(1,100):
    if rekurzija_kovanci(tabela_kovancev,i) == kovanci_dinamicna(tabela_kovancev,i):
        pass
    else:
        pravilno = False
        print(i,'NAPAČNO')
if pravilno:
    print('Prvo nalogo si naredil pravilno!')
    
pravilno = True    
for i in range(1,100):
    
    if stevilo_enic_rekurzija(i) ==  stevilo_enic_dinamicna(i):
        pass
    else:
        pravilno = False
        print(i,'NAPAČNO')
        print('Pravilna rešitev:',stevilo_enic_rekurzija(i))
        print('Tvoja rešitev:',stevilo_enic_dinamicna(i))
print('Drugo nalogo si naredil pravilno!')