¿En qué se diferencia la programación dinámica del seguimiento hacia atrás?

La programación dinámica es prácticamente un retroceso, excepto que en la programación dinámica se detienen los cálculos redundantes (que algunas personas llaman Memoization). Entonces, ¿qué quiero decir con eso?

Tomemos un problema para entender esto. Digamos que tengo que subir n escaleras y solo puedo subir 1 escalera o 2 escaleras a la vez. ¿De cuántas maneras puedo subir las n escaleras?

Una de las soluciones obvias que se te ocurrirá será dar marcha atrás (resolverlo de forma recursiva). Veamos una solución para eso en Python

# solución sin programación dinámica
def back_tracking (n_steps):
si n_steps <1: devuelve 0
elif n_steps == 1: retorno 1
elif n_steps == 2: retorno 2
de lo contrario: return back_tracking (n_steps-1) + back_tracking (n_steps-2)

Ahora puede ver que la mayoría de las llamadas de función a back_tracking() son redundantes. Un ejemplo muy simple de eso es que si tenemos que encontrar el valor para n_steps = 8, entonces tendremos que llamar a back_tracking(6) desde ambos
back_tracking(8) y back_tracking(7) . Seguir este enfoque requerirá una complejidad de tiempo O (n ^ 2). Veamos por qué la programación dinámica es única:

# solución con programación dinámica
def dynamic_programming (n_steps, method_values ​​= None):
si n_steps <1: devuelve 0
elif n_steps == 1: retorno 1
elif n_steps == 2: retorno 2
más:
# caso donde la lista de value_valor no se ha inicializado
if (method_values ​​== None):
valores_métodos = [-1] * n_pasos

# caso cuando no se ha realizado esta llamada al método
if (method_values ​​[n_steps-1] == -1):
valores_métodos [n_steps-1] = programación_ dinámica (n_steps-1, valores_métodos);
if (method_values ​​[n_steps-2] == -1):
valores_métodos [n_steps-2] = programación_ dinámica (n_steps-2, valores_métodos);

devuelve valores_métodos [n_steps-1] + valores_métodos [n_steps-2];

Como puede ver en la solución de programación dinámica antes de llamar a cualquier función, vemos que si esa función se ha llamado o no. ¡De esta manera llamamos a la función una vez y, por lo tanto, tenemos una complejidad temporal de O (n)!

Editar:
Aunque también vale la pena señalar que necesitábamos un espacio adicional de O (n) para almacenar el valor devuelto de cada llamada de función única. (Gracias a Francisco Andrades Grassi por señalar esto)