Ottieni la sum minima di una combinazione di elementi matrix

Ieri un mio amico è venuto con un problema, chiedendomi di trovare la soluzione.

Il problema

Ho una matrix(nxm) . Ho bisogno di trovare la minima quantità di ciò che posso produrre da quell'elemento matrix.

La condizione è:

  • Il count dovrebbe iniziare solo dalla cella in alto a sinistra. E
  • Dovrebbe finire nella cella in basso a destra.
  • L'algorithm dovrebbe contare tutti i possibili routes
  • In questo modo ho bisogno di trovare la minima sum ansible.

Dopo aver lottato per alcune ore, sono in grado di trovare uno schema per questo. Ma non so come implementarlo in codice.

    Ecco il mio model:

    inserisci la descrizione dell'immagine qui

    Come posso implementarlo?

    Modificare :

     $Cost = arrays(); for ($x = 0; $x < $rows; $x++) { $Cost[0][$x] = $matrix[0][$x]; for ($y = 1; $y < $cols; $y++) { $Cost[$y][0] = $matrix[$y][0]; } } for ($x = 1; $x < $rows; $x++) { for ($y = 1; $y < $cols; $y++) { $Cost[$x][$y] = intval($matrix[$x][$y]) + min(intval($Cost[$x - 1][$y]), intval($Cost[$x][$y - 1])); } } 

    Matrice matrix che sto provando:

     arrays(2) { [0]=> arrays(3) { [0]=> string(1) "3" [1]=> string(2) "44" [2]=> string(2) "75" } [1]=> arrays(3) { [0]=> string(2) "21" [1]=> string(2) "98" [2]=> string(2) "60" } } 

    Risultato:

     arrays(3) { [0]=> arrays(2) { [0]=> string(1) "3" [1]=> string(2) "44" } [1]=> arrays(3) { [0]=> string(2) "21" [1]=> int(119) [2]=> int(0) } [2]=> arrays(1) { [0]=> NULL } } 

    Sembra che tu possa andare solo a destra e in basso. In questo caso (altrimenti utilizza gli algoritmi di individuazione dei routes) nota che puoi entrare in each cella sia dalla cella superiore sia dalla cella sinistra. Il path più economico per questa cella sarà minimo rispetto a questi valori. Quindi la soluzione DP può sembrare (pseudocodice):

    vedere le correzioni qui

     Cost[0, 0] = matrix[0, 0] for x = 1 to cols - 1 Cost[0, x] = matrix[0, x] + Cost[0, x-1] //0th row for y = 1 to rows - 1 Cost[y, 0] = matrix[y, 0] + Cost[y-1, 0] //0th column //proper filling of 0th row and 0th column for y = 1 to rows - 1 for x = 1 to cols - 1 Cost[y, x] = matrix[y, x] + Min(Cost[y-1, x], Cost[y, x-1]) 

    quindi Costo [n-1, n-1] è ciò di cui hai bisogno

    Un aggiornamento alla risposta di MBo . Dato un * m (n = 3, m = 4 nel tuo post) Lo spazio consumato può essere ridotto a O (N) solo ricordando il risultato per la row precedente (colonna).

     Cost[0] = matrix[0, 0] for x = 1 to m - 1 Cost[x] = matrix[0, x] + Cost[x-1] for y = 1 to n - 1 Cost[0] += matrix[y, 0] for x = 1 to m - 1 Cost[x] = matrix[y, x] + Min(Cost[x-1], Cost[x]) output(Cost[n-1]) 

    Non so come scrivere in PHP … Ecco il codice di esempio di Python

     matrix = [ [3, 44, 75], [21, 98, 60], ] n = len(matrix) m = len(matrix[0]) cost = [0] * m cost[0] = matrix[0][0] for x in xrange(1, m): cost[x] = matrix[0][x] + cost[x-1] for y in xrange(1, n): cost[0] += matrix[y][0] for x in xrange(1, m): cost[x] = matrix[y][x] + min(cost[x-1], cost[x]) print cost[-1]