Сумма в матрице (движение по матрице вниз и вправо)

Question

Имеется задача. Нужно найти максимальную сумму в матрице двигаясь только вниз или вправо. Нужно решение с объяснением. Я сижу над этой задачкой уже несколько дней. Пытался решить с помощью графов, но у меня ничего не выходит. Выглядит очень просто, но у меня не хватает знаний. Прошу написать решение с объяснением.

Константы:
0 < n <= 100

Вот ссылка с кодом , что я имею : https://yadi.sk/d/VXZMw1l_PwHYow

Пример входа:

3                 # n Количество строк и столбцов в матрице
10 15 9           # Три строки ввода
12 3 6
20 1 17

Выход: 60

Answer 1

def f(arr, n):
    res = [[0] * n for _ in range(n)]
    res[0][0] = arr[0][0]
    for i in range(1, n):
        res[i][0] = res[i - 1][0] + arr[i][0]
        res[0][i] = res[0][i - 1] + arr[0][i]
    
    for i in range(1, n):
        for j in range(n - i):
            res[i][i + j] = max(res[i - 1][i + j], res[i][i + j - 1]) + arr[i][i + j]
            res[i + j][i] = max(res[i + j][i - 1], res[i + j - 1][i]) + arr[i + j][i]

    return res[n - 1][n - 1]

arr = [[10, 15, 9],
           [12, 3,  6],
           [20, 1, 17]]

print(f(arr, 3))

res в начале:

0 0 0
0 0 0
0 0 0

присваиваем первому элементу значение:

10 0 0
0  0 0
0  0 0

заполняем левую и верхнию грань, для левой бирем значение из arr и складывает с элементом который выше него в res, тоже самое и для верхней но бирем элемент слева:

10 25 34
22 0  0
42 0  0

постепенно заполняем остальное, беря при этом максимально большого соседа

10 25 34
22 28 40
42 43 60

Либо так с помощью рекурсии

def f(arr, n, i = 0, j = 0):
    sum_ = arr[i][j]
    
    if i + 1 < n and j + 1 < n:
        sum_ += max(
            f(arr, n, i + 1, j),
            f(arr, n, i, j + 1)
        )
    elif i + 1 < n:
        sum_ += f(arr, n, i + 1, j)
    elif j + 1 < n:
        sum_ += f(arr, n, i, j + 1)
    
    return sum_
    
arr =  [[10, 15, 9],
           [12, 3,  6],
           [20, 1, 17]]
print(f(arr, 3))

Answer 2

Существует термин "Динамическое программирование". Он связан как раз с подобными задачами, и конкретно эта является базовой задачей по теме.

Суть динамического программирования заключается в получении ответа для большого случая через решение меньших и их объединение. Например, простейшей задачей на ДП является "Кузнечик": "Кузнечик может прыгать на одну или две травинки за один раз. Сколькими различными путями он может прийти на N-ную травинку?". Для этой задачи формула ДП осень проста: dp[n] = dp[n - 1] + dp[n - 2]. Очень простая закономерность, которую можно вычислить за O(n), не перебирая все возможные пути за O(2^n) (на всякий случай скажу, что конкретная эта задача решается за O(logN), но если вам это интересно, то прочитайте в интернете сами).

В вашем случае, попробуйте считать максимальную сумму для каждой клетки, а не пытайтесь сразу прийти к ответу для конечной. Тогда для каждой конкретной ячейки вы заметите, что в нее всегда выгоднее приходить из той, в которой накопленная сумма уже больше. Данное утверждение, конечно, требует доказательств, но в данном случае у вас есть весь интернет, собственная голова и клише доказательств от противного.

В итоге, мы имеем правило dp[x][y] = max(dp[x - 1][y] + dp[x][y - 1]) + a[x][y], согласно которому можно заполнить все ячейки, кроме первой строки и первого столбца. К ячейкам из первого столбца и первой строки существует ровно один путь, так что и посчитать там заранее максимальное значение можно очевидным образом.

БЛОГ НА HUSL

Сумма в матрице (движение по матрице вниз и вправо)

Ответы (2 шт):