[Java lista] SCJP vizsga

[Zoltan Bodi]

iszekely at delfin.unideb.hu <iszekely at delfin.unideb.hu> írta, 2007.08.17.:
>
> Miert is? Van egy (m x n) meretu matrixod. Abban van (m-k+1)x(n-l+1) darab
> (k x l) meretu reszmatrixod. Aztan k=1..m es l=1..n. Ez mar igy eleg sok
> reszmatrix-osszegzest eredmenyez. Most nem vezettem vegig a kepletet, de
> ez
> igy messzirol nezve nem tunik linearis bonyolultsagu algoritmusnak. :) A
> matrix meretnek novelesevel konnyen elszaladhat az algoritmusoddal a lo.
>
> Muszaj lennie valami hatekonyabb algoritmusnak. Beirhatod, ha megvan a
> Google-tol. :)

"dynamic programming" a keresőbe ;-)

Ilyen feladatoknál az szokott lenni a trükk, hogy a többször is
felhasználható részeredményeket
csak egyszer szabad kiszámítani. (A nagyobb részmátrixokra vonatkozó optimum
kiszámításánál
valahogy fel kell használni a már korábban kiszámított optimumokat.)
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: http://javagrund.hu/pipermail/javalist/attachments/20070817/6c17fbad/attachment.html