Editorial for Caminos en la grilla

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: humbertoyusta

La principal idea es contar, para cada posición $(i, j)$ ~(i, j)~, la cantidad de caminos que empiezan en $(1, 1)$ ~(1, 1)~ y acaban en $(i, j)$ ~(i, j)~, denotemos eso como $dp_{i,j}$ ~dp_{i,j}~, si está bloqueada, simplemente es 0, de lo contrario podemos calcular esto a partir de:

Cada camino que acabe en $(i-1, j)$ ~(i-1, j)~ se le puede añadir al final la casilla $(i, j)$ ~(i, j)~.
Cada camino que acabe en $(i, j-1)$ ~(i, j-1)~ se le puede añadir al final la casilla $(i, j)$ ~(i, j)~.

Se puede notar que todos los caminos que llegan a $(i, j)$ ~(i, j)~ pasan o por $(i-1, j)$ ~(i-1, j)~ y por $(i,j-1)$ ~(i,j-1)~, así que podemos calcular $dp_{i,j}$ ~dp_{i,j}~ como la suma de $dp_{i-1,j}$ ~dp_{i-1,j}~ y $dp_{i,j-1}$ ~dp_{i,j-1}~, recuerde asegurarse de que cuando vaya a calcular $dp_{i,j}$ ~dp_{i,j}~ ya $dp_{i-1,j}$ ~dp_{i-1,j}~ y $dp_{i,j-1}$ ~dp_{i,j-1}~ estén calculados, esto se puede hacer fácil recorriendo los pares $(i, j)$ ~(i, j)~ en orden ascendente. Complejidad $O(n^2)$ ~O(n^2)~

Comments

There are no comments at the moment.