Memorización sin arreglo

En la Introducción a los algoritmos de Cormen et al. , La sección 15.3 Elementos de la programación dinámica explica la memorización de la siguiente manera:

Un algoritmo recursivo memorizado mantiene una entrada en una tabla para la solución de cada subproblema. Cada entrada de la tabla inicialmente contiene un valor especial para indicar que la entrada aún no se ha completado. Cuando el subproblema se encuentra por primera vez a medida que se desarrolla el algoritmo recursivo, su solución se calcula y luego se almacena en la tabla. Cada vez que nos encontramos con este subproblema, simplemente buscamos el valor almacenado en la tabla y lo devolvemos.

Y agrega, como nota al pie:

Este enfoque presupone que conocemos el conjunto de todos los parámetros de subproblemas posibles y que hemos establecido la relación entre las posiciones de la tabla y los subproblemas. Otro enfoque más general es memorizar mediante el uso de hashing con los parámetros del subproblema como claves.

¿Hay algún problema DP conocido que requiera (o facilite) almacenar valores memorizados en un diccionario en lugar de en una matriz (multidimensional)?

Antecedentes: si esto es de alguna utilidad, la razón de esta pregunta es que estoy tratando de motivar la noción de árboles de búsqueda binarios (autobalanceados) a las personas que acaban de ver programación dinámica.

Probablemente hay mejores ejemplos, pero aquí hay uno, fuera de mi cabeza:

$S,T$$\le d$$>d$

Me gustaría proporcionar 2 ejemplos.

0-1 problema de mochila

En el caso del problema 0-1 Mochila (donde W es la capacidad de la mochila y N es una cantidad de elementos), a veces es mejor usar la Programación dinámica de arriba hacia abajo con la memorización, en lugar de la enumeración sistemática de abajo hacia arriba de toda la matriz 2D de tamaño WxN (especialmente en un caso en que la capacidad de la mochila W es grande, pero la cardinalidad del conjunto de combinaciones permitidas de pesos de artículos es mucho menor que W ).

En este caso, en aras de la economía de una memoria, uno puede optar por utilizar el diccionario para la memorización en lugar de la matriz 2D.

Algoritmo de análisis Earley

El algoritmo de análisis Earley se puede utilizar para analizar declaraciones, que pertenecen a una gramática libre de contexto. A diferencia de la algoritmo CYK (que se basa en el enfoque DP de abajo hacia arriba y usa una tabla 2D para la memorización), el analizador Earley usa el enfoque de arriba hacia abajo en combinación con el gráfico de análisis para la memorización.

El gráfico de análisis contiene las producciones gramaticales parcialmente analizadas (p. Ej., Dada la producción X → AB , y después de la coincidencia exitosa del parte A de esta producción, almacenamos la producción parcialmente coincidente dentro del gráfico de análisis: X → A • B , donde los puntos de puntos a la parte ya emparejada).

La cantidad de columnas dentro del gráfico de análisis igual a la cantidad de tokens. Sin embargo, en el caso general, puede ser muy complicado estimar la cantidad de producciones gramaticales parcialmente analizadas por columna (depende de la gramática y la secuencia particular de los tokens).

Por lo tanto, es más conveniente implementar el gráfico de análisis basado en la estructura de datos del diccionario.

En el dominio de Procesamiento del lenguaje natural, por lo general, Earley pareser es la opción más conveniente, ya que no requiere la forma normal de Chomsky para la gramática (y CYK tiene ese requisito).

En mi experiencia con la programación competitiva, usar una tabla hash (Python dicto similar) a menudo es más conveniente que usar una matriz, porque cualquier tipo de datos hashaable se puede usar como clave, como cadenas, conjuntos ( frozenseten Python) o tuplas como(string, int) etc. Si usa una matriz, debe traducir manualmente todas las claves a enteros (comenzando en 0), lo que requiere trabajo adicional y, como sus notas de origen, puede no ser posible si no conoce el espacio de las claves de antemano. Por lo tanto, los diccionarios son bastante más generales que las matrices.

Por supuesto, si puede salirse con la suya usando matrices, probablemente sea más rápido porque evita calcular hashes repetidamente (por otro lado, requiere inicializar toda la matriz primero, lo que lleva tiempo y memoria), pero puede llevar más tiempo escribir el código porque tienes que hacer el trabajo extra de traducir todas las claves a enteros.