Programación Dinámica

import math

def f(d,p,C,S):
    if p <= 0:
        C[0] = 0
        return
    f(d,p-1,C,S)
    conteo = math.inf
    moneda = 0
    for di in d:
        if di <= p:
            if C[p-di] < conteo:
                conteo = C[p-di]
                moneda = di
    C[p] = conteo + 1
    S[p] = moneda

def monedas(d, n):
    C = [-1] * (n + 1)
    S = [0] * (n + 1)
    f(d,n,C,S)
    return C, S

monto = 19
c, s = monedas([1, 5, 10, 20, 25, 50], monto)
print(c)
print(s)
contar = [0] * (monto + 1)
while monto > 0:
    print(s[monto],monto)
    contar[s[monto]] += 1
    monto -= s[monto]

for x in range(len(contar)):
    if contar[x] > 0:
        print("Hay " + str(contar[x]) + " monedas de " + str(x))

FIBONACCI

import math

cont = [0]
def fibo(n):
    t = [0]*(n+1)
    def fibofibo(n):
        cont[0] += 1
        if n == 1:
            t[0] = 0
            t[1] = 1
        else:
            fibofibo(n - 1)
            t[n] = t[n-1] + t[n-2]
    fibofibo(n)
    return t[n]

n = 10
print("Fibonacci de %d es %d"%(n, fibo(n)))
print("Iteraciones: %d"%(cont[0]))

def mincoins(d, p):
    C = [0]*(p + 1)
    M = [0]*(p + 1)

    def recu(p):
        if p == 0:
            C[0] = 0
        else:
            recu(p - 1)
            Cother = []
            minimum = math.inf
            moneda = 0
            for di in d:
                if p - di >= 0 and C[p-di] < minimum:
                    minimum = C[p-di]
                    moneda = di

            C[p] = 1 + minimum
            M[p] = moneda

    recu(p)
    return C, M

d = [1, 5, 10, 20, 25, 50]
p = 40
C, M = mincoins(d, p)
print(C)
print(M)