Semanas 14 y 15 Programacion Dinamica

Semanas 14 y 15: Programación Dinámica

Objetivo

Pasar de recursión a memoización o tabulación, definiendo estado, transición, casos base y orden de cómputo antes de codificar.

Problemas Completados

Problema	Patrón	Función	Tests
Climbing Stairs	DP 1D con compresión	climb_stairs	2
Min Cost Climbing Stairs	Minimización DP 1D	min_cost_climbing_stairs	2
House Robber	Decisión DP 1D	house_robber	2
House Robber II	División de ciclo en dos rangos	house_robber_circular	2
Coin Change	Minimización DP 1D	coin_change	3
Decode Ways	DP 1D con ceros	decode_ways	3
Longest Increasing Subsequence	Tails + búsqueda binaria	longest_increasing_subsequence	2
Word Break	DP de prefijos	word_break	2
Unique Paths	DP de grid con compresión	unique_paths	2
Longest Common Subsequence	DP 2D con compresión	longest_common_subsequence	2
Edit Distance	DP 2D con compresión	edit_distance	2
Longest Palindromic Subsequence	DP de intervalos	longest_palindromic_subsequence	2
Partition Equal Subset Sum	Knapsack 0/1	can_partition	3
Best Time to Buy and Sell Stock with Cooldown	DP de estados finitos	max_profit_with_cooldown	2
House Robber III	DP en árbol	house_robber_tree	2
Target Sum	Transformación a conteo de subconjuntos	target_sum_ways	2
Combination Sum IV	Conteo ordenado	combination_sum_iv	2
Maximum Product Subarray	Máximo y mínimo local	maximum_product_subarray	2
Minimum Path Sum	DP de grid con compresión	minimum_path_sum	2
Distinct Subsequences	Conteo de subsecuencias	distinct_subsequences	2

Ideas Clave

DP 1D con Compresión

Se usa cuando el estado actual solo necesita uno o dos estados anteriores.

Ejemplos:

• climb_stairs
• min_cost_climbing_stairs
• house_robber
• house_robber_circular
• decode_ways

Invariante:

• Antes de avanzar, las variables comprimidas representan exactamente los estados anteriores necesarios.

Minimización DP

En coin_change, dp[amount] guarda la menor cantidad de monedas para formar ese monto.

Invariante:

• Un valor centinela marca montos todavía inalcanzables.
• Cada moneda intenta mejorar el estado actual desde un submonto ya calculado.
• En costo mínimo de escaleras, solo importa el costo mínimo para llegar a los dos escalones previos.

DP de Prefijos

En word_break, dp[i] indica si input[..i] puede segmentarse con palabras del diccionario.

Invariante:

• Si existe un start válido y input[start..end] está en el diccionario, entonces dp[end] es verdadero.

DP 2D con Compresión

En unique_paths, longest_common_subsequence y edit_distance, se conserva solo la fila necesaria.

Invariante:

• La fila anterior representa estados ya cerrados.
• La fila actual se construye de izquierda a derecha cuando depende del estado izquierdo.

DP de Intervalos

En longest_palindromic_subsequence, cada estado representa el mejor resultado dentro de input[left..=right].

Invariante:

• Si los extremos coinciden, extienden el mejor resultado interno.
• Si no coinciden, se descarta uno de los extremos y se conserva el mejor subintervalo.

Knapsack 0/1

En can_partition, cada número puede usarse una sola vez.

Invariante:

• Recorrer el objetivo en reversa evita reutilizar el mismo número dentro de la misma iteración.

Tails para LIS

En longest_increasing_subsequence, tails[i] guarda el menor final posible para una subsecuencia de longitud i + 1.

Invariante:

• tails permanece ordenado.
• Reemplazar un valor no cambia la longitud encontrada, pero mejora opciones futuras.

DP de Estados Finitos

En max_profit_with_cooldown, cada día termina en uno de tres estados:

• hold: se conserva una acción.
• rest: no se tiene acción y se puede comprar.
• cooldown: se acaba de vender y el siguiente día no puede comprar desde ese estado.

Invariante:

• Comprar solo puede salir de rest.
• Vender solo puede salir de hold.
• rest toma lo mejor entre seguir descansando o terminar el cooldown anterior.

DP en Árbol

En house_robber_tree, cada nodo devuelve dos estados: robarlo o saltarlo.

Invariante:

• Si se roba el nodo actual, los hijos deben saltarse.
• Si se salta el nodo actual, cada hijo elige su mejor estado.

Conteo con Transformación

target_sum_ways transforma signos positivos y negativos en un conteo de subconjuntos.

Invariante:

• Si sum + target es impar o negativo, no existe partición válida.
• Recorrer en reversa evita reutilizar un número.
• Los ceros duplican el número de formas, porque +0 y -0 son asignaciones distintas.

Conteo Ordenado

En combination_sum_iv, el orden importa.

Invariante:

• dp[amount] suma todas las secuencias que terminan con cada candidato.
• El ciclo externo debe ser el monto para permitir permutaciones distintas.

Máximo Producto

maximum_product_subarray mantiene el mejor y el peor producto que terminan en la posición actual.

Invariante:

• Un número negativo puede convertir el peor producto local en el mejor.
• Un cero reinicia el producto y también puede ser la mejor respuesta si todo lo demás es negativo.

Representación en Rust

Vector de estados:

Vec<i32>

Conteos grandes antes de devolver:

Vec<i64>

Estados booleanos:

Vec<bool>

Diccionario para segmentación:

HashSet<&str>

Errores Comunes

• Empezar a codificar sin definir qué significa dp[i].
• Usar recursión sin memoización cuando los subproblemas se repiten.
• En knapsack 0/1, recorrer hacia adelante y reutilizar accidentalmente el mismo elemento.
• Olvidar tratar 0 como caso especial en Decode Ways.
• En LCS, sobrescribir estados antes de usarlos si no se separa fila previa y fila actual.
• En problemas circulares, olvidar que elegir el primer elemento excluye el último.
• En DP de intervalos, llenar la tabla en un orden que lee estados todavía no calculados.
• En cooldown, permitir comprar justo después de vender.
• En Target Sum, olvidar que los ceros multiplican las formas.
• En Maximum Product Subarray, guardar solo el máximo local y perder el efecto de negativos.

Verificación

cargo test

Resultado al cerrar el bloque:

399 passed; 0 failed

Siguiente Bloque

El siguiente bloque recomendado es:

• Heaps.
• Intervalos.
• Greedy.

Primeros problemas sugeridos:

• Merge K Sorted Lists.
• K Closest Points con heap.
• Meeting Rooms II.
• Minimum Number of Arrows to Burst Balloons.