Az eredeti feladat itt.

Megoldás

Ez egy meglehetősen sztenderd dinamikus programozási feladat. Jelöljük F(i,j)-vel azt, hogy az i-edik mezőről indulva hányféleképp juthatunk el az N-edikre legfeljebb j dobással. Mindössze annyit kell észrevennünk, hogy teljesül a következő rekurzió:

F(i,j) = F(i+1,j-1) + F(i+2,j-1) + F(i+3,j-1) + F(i+4,j-1) + F(i+5,j-1) + F(i+6,j-1)

feltéve persze, hogy i <= N-6. Hiszen azon esetek száma, amikor első dobásként k-t dobunk, pontosan F(i+k,j-1)-gyel egyenlő. Ha i közel van N-hez, ugyanezen gondolatmenettel akkor is felírható egy hasonló képlet (ami kicsit kuszább lesz ennél), de azt is észrevehetjük, hogy i > N-6-ra F(i,j) = 5 * F(i,j-1) + 1. Arra is figyeljünk oda, hogy F(N,j) = 1 minden j-re. A válasz, amit keresünk F(1,K).

Tehát a dinamikus megoldás az összes F(i,j) érték kiszámolásával történik, az F(i,0) = 0 (i<N) illetve F(N,j) = 1 kezdőfeltételek mellett. Ezt kisebb adatokra egy N-szer K-s tömbben is megoldhatnánk, itt azonban ehhez nincs elég memória, meg hát amúgy sincs szükség rá: egy egydimenziós, N elemű tömbben is megoldható az egész, ha rögzített j-re az i-ken növekvő sorrendben megyünk végig. (Ekkor ugyanis nyugodtan felülírhatjuk az F(i,j-1) értéket F(i,j)-vel, nem vész el a későbbiekben szükséges információ.)

A futásidő tehát O(NK), míg a memóriából csak N-nel arányosan foglaltunk.

Megoldásom (nem a hivatalos megoldás!)

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.