Defina el estado y la transición

Toda DP comienza por definir un estado: ¿qué representa realmente dp[i]? Escriba correctamente esta frase y el resto se deducirá de ella.

Escriba el significado con palabras: dp[i] = la respuesta para los primeros i elementos. Una definición de estado imprecisa conduce a una recurrencia defectuosa.

La transición indica cómo se construye dp[i] a partir de estados anteriores. Es la ecuación de recurrencia central de su solución.

Los casos base son los estados más pequeños que conoce directamente. Sin anclas correctas, todos los valores posteriores se desviarán.

Cada estado debe rellenarse después de los estados de los que depende. Esta regla de dependencias determina la dirección de los bucles.

Decida qué celda contiene el resultado final. A menudo es dp[n], pero a veces es el máximo de toda la tabla.

El número de estados distintos establece su presupuesto de tiempo. Una DP unidimensional sobre n elementos tiene O(n) estados que rellenar.

El tiempo total es el número de estados multiplicado por el trabajo de cada transición. Una transición O(n) dentro de n estados produce O(n al cuadrado).

Si un índice no puede representar la situación, añada otro. Una segunda dimensión convierte dp[i] en dp[i][j].

Para recuperar la solución real, guarde qué transición ganó en cada estado y, después, recorra el camino hacia atrás desde la respuesta.

Estado, transición, caso base, orden y respuesta. Defina con precisión esos cinco elementos y casi cualquier recurrencia de DP se vuelve evidente.

Está diseñando una DP. ¿Qué representa dp[i]?

Ahora puede definir un estado, escribir su transición, establecer los casos base y localizar la respuesta. Ese esquema convierte la DP de un proceso de adivinanzas en una receta.