Estoy tratando de resolver un problema que es una variante de una sola fila derompecabezas de rascacielos. La declaración del problema es:

Considere una sola fila de un rompecabezas de rascacielos de tamaño nxn. Si sabemos cuántos edificios se pueden ver desde la izquierda y desde la derecha de la fila, ¿cuántas maneras diferentes hay de poblar esa fila con edificios de alturas 1..n? (1 <= n <= 5000)

Lo estoy resolviendo con la programación dinámica ascendente. La relación de recurrencia es la siguiente:

f(n,left,right)=(n-2)*f(n-1,left,right) + f(n-1,left-1,right) +f(n-1,left,right-1)
f[1][1][1]=1;

No se preocupe por los números grandes en la respuesta, ya que se supone que debo mostrar el resultado del módulo. Puedo obtener una respuesta correcta de esto, pero el requisito de memoria para este algoritmo es muy alto. La complejidad espacial para esto será O (n ^ 3), que es demasiado para un problema dado, ya que n puede ser hasta 5,000.

¿Me puede sugerir algún algoritmo alternativo?

Editar:

Para una explicación de mi relación de recurrencia: considere todas las combinaciones con (n-1) altura y ahora agregue 1 altura a todo el edificio. Esto nos dará edificios de 2,3 a n. Ahora solo se debe ajustar el edificio con altura 1. Se puede ajustar en ambos lados, que es el segundo y el tercer término además. Si se inserta no en los lados, entonces eso está representado por el primer término además. Avíseme si aún no está claro, realmente agradecería cualquier ayuda