Toate săriturile merg spre dreapta/jos, deci grila e un DAG și facem DP de la (1,1). Săriturile de lungime variabilă (până la P, Q, R) se accelerează: sume parțiale pentru numărul de moduri (C2), minim pe fereastră glisantă pentru numărul minim de sărituri (C1). Săritura calului adaugă două tranziții fixe.
Vezi enunțul oficialÎncearcă întâi singur! Indiciile elimină din satisfacția rezolvării.
Cheia e că țurcana nu poate da niciodată înapoi: orice săritură crește linia, coloana sau ambele. Asta înseamnă că, atunci când completăm celula , toate celulele din care s-ar putea ajunge la ea sunt deja calculate. Putem deci umple grila o singură dată, linie cu linie, de la spre — un DP clasic pe grilă.
Conectează-te ca să marchezi problemele rezolvate.