17. Выше таблицы размером n×m находится черепашка, которая начинает свой путь в левом верхнем углу. В каждой клетке

Добро пожаловать! Для решения данной задачи, мы можем использовать динамическое программирование. Позвольте мне объяснить процесс шаг за шагом.

Давайте создадим двумерный массив \(dp\) размером \(n \times m\), где каждый элемент будет хранить наибольшую возможную сумму чисел в клетках черепашки, проходящих через текущую клетку.

Итак, начнем с заполнения первой строки и первого столбца массива \(dp\). Для первой строки, пусть \(dp[0][j]\) будет равно сумме всех чисел в клетках этой строки до индекса \(j\). Аналогично, для первого столбца, пусть \(dp[i][0]\) будет равно сумме всех чисел в клетках этого столбца до индекса \(i\). Это позволит нам иметь базовую информацию о суммах для каждой клетки, через которую проходит черепашка.

Теперь, чтобы заполнить остальные ячейки массива \(dp\), мы будем использовать следующий рекуррентный шаг. Для каждой клетки \((i, j)\) в массиве \(dp\), наша задача - найти наибольшую сумму чисел из клеток, которые находятся слева (\(dp[i][j-1]\)) и сверху (\(dp[i-1][j]\)). Мы затем добавим текущее число в этой клетке. То есть, мы можем записать \(dp[i][j] = \max(dp[i][j-1], dp[i-1][j]) + \text{число в клетке } (i, j)\).

Повторяя этот шаг для всех ячеек массива \(dp\) от начала до конца, мы в конце получим наибольшую возможную сумму чисел в клетках, через которые пройдет черепашка, включая начальную и конечную клетки.

Теперь давайте обсудим маршрут, по которому будет достигнута эта сумма. Мы можем начать с клетки \((n-1, m-1)\) (правый нижний угол) и двигаться вверх или влево на основе значений в ячейках массива \(dp\). Если значение \(\text{число в клетке } (i, j) + dp[i][j-1]\) больше значения \(\text{число в клетке } (i, j) + dp[i-1][j]\), то наш следующий шаг будет влево. В противном случае, мы двигаемся вверх.

Давайте реализуем это решение в коде чтобы посмотреть, как это работает.