Zdobądź przynajmniej sumę kombinacji elementów matrycy

Question

Wczoraj jeden z moich znajomych przyszedł z problemem, prosząc mnie, abym znalazł rozwiązanie.

Problem

Mam matrix(n x m). Muszę znaleźć najmniejszą sumę, co mogę wytworzyć z tego elementu macierzy.

Warunkiem jest:

• Liczenie powinno się rozpocząć dopiero od lewej górnej komórki. I
• Powinieneś kończyć się w dolnej prawej komórce.
• Algorytm powinien policzyć wszystkie możliwe ścieżki.
• W ten sposób muszę znaleźć możliwą najmniejszą sumę.

Po kilku godzinach szukam wzoru na to. Ale nie wiem, jak zaimplementować go w kodzie.

Oto mój wzór:

Jak mogę zaimplementować to?

Edit:

$Cost = array(); 
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])); 
    } 
} 

tablica Matrix Staram:

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

Wynik:

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

Answer 1

Wydaje się, że można przejść tylko w prawo iw dół kierunkach . W tym przypadku (w przeciwnym razie użyj algorytmów ustalania ścieżek) zauważ, że możesz wejść do każdej komórki z górnej komórki lub z lewej komórki. Najtańsza ścieżka do tej komórki będzie minimalna od tych wartości. Więc rozwiązanie DP może wyglądać (Pseudokod):

zobaczyć korekt tutaj

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]) 

następnie Koszt [n-1, n-1] jest to, czego potrzebujesz

Answer 2

aktualizację MBO - odpowiedź. Biorąc pod uwagę n * m (n = 3, m = 4 w twoim poście) Spożycie przestrzeni można zmniejszyć do O (N), pamiętając tylko wynik z poprzedniej linii (kolumny).

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]) 

nie wiem jak napisać w PHP ... Oto pyton przykładowy kod

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]