day32 programación dinámica

Introducción a la programación dinámica

¿Qué tipologías de problemas se resuelven con programación dinámica?

1. Problemas básicos
2. Problemas de la mochila (preparación para entrevistas)
3. El problema de robbing houses
4. Problemas de la股子序列
5. Otros problemas complejos

Cuestiones clave para resolver problemas con programación dinámica

1. Definición del array dp y significado de los subíndices y su inicialización.

• El array dp[\i] representa el valor que se obtiene al resolver el problema hasta el subíndice i.
• Es importante definir corectamente la significación de cada subíndice y cómo inicializar el array.

2. Fórmula de recursión.
3. Orden de recorrido del array.
4. Imprimir el array dp para depurar.

lc509 número de fibonacci

Dado un número entero n, devuelve el enésimo número de Fibonacci.

El número de Fibonacci se define como la suma de los dos números anteriores, comenzando con 0 y 1.

Enfoque recursivo:

public int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Optimización con porgramación dinámica:

public int fib(int n) {
    if (n <= 1) {
        return n;
    }
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

lc70 subir escaleras

Supongamos que estás subiendo una serie de pasos. Necesitarás n pasos para reaching la piso final.

Cada vez puedes subir 1 o 2 pasos. ¿De cuántas maneras diferentes puedes subir a la piso final?

Nota: n es un entero positivo.

Ejemplos:

• Si hay un piso, solo un método para subir.
• Si hay dos piso, dos métodos: 1+1 o 2.
• Tres piso: 1+1+1, 1+2, 2+1 → tres métodos.
• Cuatro piso: 2+2, 1+1+2, 1+2+1, 2+1+1 → cinco métodos.

Enfoque de programación dinámica:

int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

lc746 gasto mínimo subir escaleras

Dado un array de alturas (cost) donde cada subíndice representa un piso y el valor es el gasto necesario para subir a ese piso.

Cada vez que subas un piso, el costo se suma al total. Una vez pagado el costo, puedes subir 1 o 2 pasos.

Encuentra el gasto mínimo para llegar a la piso final.

Ejemplo: costt = [10, 15, 20] → la piso final es el 3 (longitud del array +1).

Enfoque de programación dinámica:

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}