Dada una cuadrícula N-por-M llena de números positivos, ¿cuál es el mejor programa para encontrar la ruta de arriba a la izquierda a la derecha que minimiza la suma de todos los números?

(Nota: no estoy seguro de si este tipo de problemas de tarea / rompecabezas de la empresa son para lo que Quora es. Tal vez tenga una regla que diga “Responda como si fuera un TA para la clase”)

La mayoría de la gente piensa primero en usar la programación dinámica de manera directa en la matriz original. Deberías probar eso y / o revisar las veces O para ver que lleva mucho tiempo incluso en algo así como una matriz de 25 × 25.

Un mejor método es usar programación dinámica para almacenar en caché los resultados, comenzando desde la parte inferior derecha. Construya la matriz de caché considerando cómo usar los vecinos de una celda de manera más efectiva y luego su respuesta estará en la celda superior izquierda de la matriz de caché.

Una explicación más profunda:
Instanciar una matriz de caché C que también es NxM st C (N, M) = B (N, M).
Ahora, recorra las celdas de B de la siguiente manera. Comience con la celda en (N, M) y avance hacia atrás a lo largo de esa fila hasta llegar a (N, 1). Luego comience nuevamente en (N-1, M) y haga lo mismo.
Mientras realiza el bucle, haga lo siguiente:
si la celda B (J, K) no tiene vecinos, entonces continúe.
si la celda B (J, K) no tiene vecino debajo de ella, entonces C (J, K) = B (J, K) + B (J, K + 1).
si la celda B (J, K) no tiene vecino a su derecha, entonces C (J, K) = B (J, K) + B (J + 1, K).
finalmente, si la celda B (J, K) tiene un vecino a su derecha y debajo de ella, entonces C (J, K) = B (J, K) + Min (C (J, K + 1), C (J + 1, K)).

Cuando haya terminado, habrá construido una matriz que tiene todas las rutas máximas a partir de cualquier celda. Su respuesta será el número en la esquina superior izquierda.