Programación dinámica II: alineamiento de secuencias, ARN y Bellman-Ford

Segunda parte de programación dinámica (capítulo 6 del Kleinberg-Tardos): tres problemas donde un solo índice no alcanza. Alineamiento de secuencias (Needleman-Wunsch): costo por hueco y desajuste, los tres casos, la recurrencia sobre prefijos de dos cadenas, el ejemplo gato/gasto con tabla y reconstrucción, la alineación como camino mínimo en una grilla y la versión en espacio lineal. Estructura secundaria del ARN: las reglas, por qué fallan los prefijos, programación dinámica sobre intervalos, orden por largo creciente y costo O(n³). Caminos mínimos con costos negativos: por qué falla Dijkstra, ciclos negativos, el algoritmo de Bellman-Ford con su recurrencia OPT(i, v), traza, costo O(n·m), espacio O(n) y detección de ciclos negativos. Capítulos 0:00 Introducción 0:24 Mapa del video 0:41 La receta de la programación dinámica 1:01 Alinear dos palabras 1:19 Costo de una alineación 1:43 Lo último que pudo pasar: tres casos 2:06 La recurrencia del alineamiento 2:28 Casos base y tabla 2:48 Ejemplo: gato y gasto 3:13 Reconstruir la alineación 3:30 Alinear = camino mínimo en una grilla 3:48 ¿Y la memoria? Espacio lineal 4:08 Resumen parcial 4:20 El ARN se pliega 4:39 Reglas de la estructura secundaria 4:59 Por qué no alcanzan los prefijos 5:23 Subproblemas sobre intervalos 5:41 La recurrencia del ARN 5:59 Orden de llenado y costo O(n³) 6:16 Ejemplo: ACCGGUAGU 6:36 Resumen parcial 6:49 Costos negativos: por qué falla Dijkstra 7:10 Ciclos negativos 7:28 El subproblema de Bellman-Ford 7:45 La recurrencia de Bellman-Ford 8:05 La traza 8:21 Costo O(n·m) y memoria 8:41 Detectar ciclos negativos 8:58 Los tres, lado a lado 9:20 Errores comunes 9:41 Resumen Video explicativo hecho con animaciones generadas por código y narración con voz sintética (IA). Si encontrás un error, dejalo en los comentarios. #DiseñoDeAlgoritmos #ProgramacionDinamica #BellmanFord #Algoritmos