Какой будет путь с максимальной стоимостью, проходящий через левый верхний угол прямоугольной таблицы размером N×M?

Задача: Путь с максимальной стоимостью в таблице

Инструкция: Чтобы найти путь с максимальной стоимостью, проходящий через левый верхний угол прямоугольной таблицы размером N×M, мы можем использовать динамическое программирование. Создадим новую таблицу dp размером N×M, где dp[i][j] будет представлять максимальную стоимость пути, проходящего через клетку (i, j).

Значения dp[i][j] можно вычислить следующим образом:
- Для клетки (0, 0) - dp[0][0] = таблица[0][0]
- Для первой строки (0 ≤ j < M) - dp[0][j] = dp[0][j-1] + таблица[0][j]
- Для первого столбца (0 ≤ i < N) - dp[i][0] = dp[i-1][0] + таблица[i][0]
- Для остальных клеток (1 ≤ i < N, 1 ≤ j < M) - dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + таблица[i][j]

Таким образом, после заполнения всей таблицы dp, максимальная стоимость пути будет находиться в dp[N-1][M-1]. Путь можно восстановить, идя по наиболее выгодным клеткам - начиная с dp[N-1][M-1] и двигаясь в обратном направлении, выбирая максимальное значение dp[i-1][j] или dp[i][j-1] для перехода в предыдущую клетку.

Например:

Пусть у нас есть таблица размером 3×3:

2 1 3

4 0 1

2 5 2

В этом случае, путь с максимальной стоимостью будет проходить через клетки (0, 0), (1, 0), (2, 0), (2, 1), (2, 2) и иметь сумму чисел равную 14.

Совет: При решении такой задачи, помните о том, что черепашка может двигаться только вправо или вниз. Это означает, что если мы находимся в клетке (i, j), то единственные возможные пути, которые приведут нас в эту клетку, могут быть либо из клетки (i-1, j), либо из клетки (i, j-1). Не забывайте использовать эту особенность при заполнении таблицы dp.

Дополнительное задание: Допустим, у нас есть таблица размером 4×5:

3 7 9 2 1

5 8 2 4 6

1 6 5 3 0

9 2 0 1 2

Какой будет путь с максимальной стоимостью? Какая будет сумма чисел в клетках на этом пути?