Programación dinámica

from functools import cache


@cache                                          # de arriba abajo: Python apunta cada resultado solo
def formas(n):
    if n <= 1:
        return 1                                # 0 o 1 escalón: una sola forma
    return formas(n - 1) + formas(n - 2)        # el último paso fue de 1 o de 2


def tabla(n):
    """De abajo arriba (tabulación): se rellena la tabla desde los casos pequeños, sin recursividad."""
    dp = [1, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp


print("Formas de subir 10 escalones de 1 en 1 o de 2 en 2:", formas(10))
print("La tabla, de 0 a 10 escalones:", tabla(10))

const memo = new Map();

/** De arriba abajo (memoización): la recursividad de siempre, apuntando cada resultado. */
function formas(n) {
    if (n <= 1) return 1;                           // 0 o 1 escalón: una sola forma
    if (memo.has(n)) return memo.get(n);
    const r = formas(n - 1) + formas(n - 2);        // el último paso fue de 1 o de 2
    memo.set(n, r);
    return r;
}

/** De abajo arriba (tabulación): se rellena la tabla desde los casos pequeños, sin recursividad. */
function tabla(n) {
    const dp = [1, 1];
    for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp;
}

console.log("Formas de subir 10 escalones de 1 en 1 o de 2 en 2: " + formas(10));
console.log("La tabla, de 0 a 10 escalones: [" + tabla(10).join(", ") + "]");

using System;

class Program {
    static readonly long[] memo = new long[11];

    // De arriba abajo (memoización): la recursividad de siempre, apuntando cada resultado.
    static long Formas(int n) {
        if (n <= 1) return 1;                           // 0 o 1 escalón: una sola forma
        if (memo[n] != 0) return memo[n];
        return memo[n] = Formas(n - 1) + Formas(n - 2); // el último paso fue de 1 o de 2
    }

    // De abajo arriba (tabulación): se rellena la tabla desde los casos pequeños, sin recursividad.
    static long[] Tabla(int n) {
        var dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp;
    }

    static void Main() {
        Console.WriteLine("Formas de subir 10 escalones de 1 en 1 o de 2 en 2: " + Formas(10));
        Console.WriteLine("La tabla, de 0 a 10 escalones: [" + string.Join(", ", Tabla(10)) + "]");
    }
}

<?php
$memo = [];

/** De arriba abajo (memoización): la recursividad de siempre, apuntando cada resultado. */
function formas(int $n): int {
    global $memo;
    if ($n <= 1) return 1;                          // 0 o 1 escalón: una sola forma
    return $memo[$n] ??= formas($n - 1) + formas($n - 2);   // el último paso fue de 1 o de 2
}

/** De abajo arriba (tabulación): se rellena la tabla desde los casos pequeños, sin recursividad. */
function tabla(int $n): array {
    $dp = [1, 1];
    for ($i = 2; $i <= $n; $i++) $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    return $dp;
}

echo "Formas de subir 10 escalones de 1 en 1 o de 2 en 2: " . formas(10) . "\n";
echo "La tabla, de 0 a 10 escalones: [" . implode(", ", tabla(10)) . "]\n";

def cambio(monedas, cantidad):
    """El mínimo de monedas para pagar cantidad, y cuáles. dp[v] = mínimo para pagar v."""
    INF = float("inf")
    dp = [0] + [INF] * cantidad
    ultima = [0] * (cantidad + 1)
    for v in range(1, cantidad + 1):
        for m in monedas:
            if m <= v and dp[v - m] + 1 < dp[v]:
                dp[v] = dp[v - m] + 1
                ultima[v] = m                   # se apunta la moneda para poder reconstruir
    if dp[cantidad] == INF:
        return f"{cantidad}: imposible"
    usadas, v = [], cantidad
    while v > 0:
        usadas.append(str(ultima[v]))
        v -= ultima[v]
    return f"{cantidad} = {' + '.join(usadas)} ({dp[cantidad]} monedas)"


print(cambio([1, 3, 4], 6))
print(cambio([1, 5, 10, 25], 63))
print(cambio([5, 2], 3))

/** El mínimo de monedas para pagar cantidad, y cuáles. dp[v] = mínimo para pagar v. */
function cambio(monedas, cantidad) {
    const dp = new Array(cantidad + 1).fill(Infinity), ultima = new Array(cantidad + 1).fill(0);
    dp[0] = 0;
    for (let v = 1; v <= cantidad; v++)
        for (const m of monedas)
            if (m <= v && dp[v - m] + 1 < dp[v]) {
                dp[v] = dp[v - m] + 1;
                ultima[v] = m;                     // se apunta la moneda para poder reconstruir
            }
    if (dp[cantidad] === Infinity) return `${cantidad}: imposible`;
    const usadas = [];
    for (let v = cantidad; v > 0; v -= ultima[v]) usadas.push(ultima[v]);
    return `${cantidad} = ${usadas.join(" + ")} (${dp[cantidad]} monedas)`;
}

console.log(cambio([1, 3, 4], 6));
console.log(cambio([1, 5, 10, 25], 63));
console.log(cambio([5, 2], 3));

using System;
using System.Collections.Generic;

class Program {
    // El mínimo de monedas para pagar cantidad, y cuáles. dp[v] = mínimo para pagar v.
    static string Cambio(int[] monedas, int cantidad) {
        int[] dp = new int[cantidad + 1], ultima = new int[cantidad + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        for (int v = 1; v <= cantidad; v++)
            foreach (int m in monedas)
                if (m <= v && dp[v - m] != int.MaxValue && dp[v - m] + 1 < dp[v]) {
                    dp[v] = dp[v - m] + 1;
                    ultima[v] = m;                     // se apunta la moneda para poder reconstruir
                }
        if (dp[cantidad] == int.MaxValue) return 
quot;{cantidad}: imposible";
        var usadas = new List<int>();
        for (int v = cantidad; v > 0; v -= ultima[v]) usadas.Add(ultima[v]);
        return 
quot;{cantidad} = {string.Join(" + ", usadas)} ({dp[cantidad]} monedas)";
    }

    static void Main() {
        Console.WriteLine(Cambio(new[] { 1, 3, 4 }, 6));
        Console.WriteLine(Cambio(new[] { 1, 5, 10, 25 }, 63));
        Console.WriteLine(Cambio(new[] { 5, 2 }, 3));
    }
}

<?php
/** El mínimo de monedas para pagar $cantidad, y cuáles. $dp[$v] = mínimo para pagar $v. */
function cambio(array $monedas, int $cantidad): string {
    $dp = array_fill(0, $cantidad + 1, PHP_INT_MAX);
    $ultima = array_fill(0, $cantidad + 1, 0);
    $dp[0] = 0;
    for ($v = 1; $v <= $cantidad; $v++)
        foreach ($monedas as $m)
            if ($m <= $v && $dp[$v - $m] !== PHP_INT_MAX && $dp[$v - $m] + 1 < $dp[$v]) {
                $dp[$v] = $dp[$v - $m] + 1;
                $ultima[$v] = $m;                  // se apunta la moneda para poder reconstruir
            }
    if ($dp[$cantidad] === PHP_INT_MAX) return "$cantidad: imposible";
    $usadas = [];
    for ($v = $cantidad; $v > 0; $v -= $ultima[$v]) $usadas[] = $ultima[$v];
    return "$cantidad = " . implode(" + ", $usadas) . " ({$dp[$cantidad]} monedas)";
}

echo cambio([1, 3, 4], 6), "\n";
echo cambio([1, 5, 10, 25], 63), "\n";
echo cambio([5, 2], 3), "\n";