Динамическое программирование. Информатика

83

Эта задача решается методом динамического программирования. Создадим квадратную матрицу dp размера 5 на 5, где dp[i][j] - это максимальное количество конфет, которое Сладкоежка может собрать, перемещаясь из клетки (1,1) в клетку (i,j). Первоначально dp[1][1] равно количеству конфет в клетке (1,1). Затем мы заполняем первую строку и первый столбец матрицы dp. Для клетки (1,j) (j>1) мы можем попасть только из клетки (1,j-1) движением вправо, поэтому dp[1][j] = dp[1][j-1] + количество конфет в клетке (1,j). Аналогично для клетки (i,1) (i>1) мы можем попасть только из клетки (i-1,1) движением вниз, поэтому dp[i][1] = dp[i-1][1] + количество конфет в клетке (i,1). Для всех остальных клеток (i,j) (i>1, j>1) мы можем попасть либо из клетки (i-1,j) движением вниз, либо из клетки (i,j-1) движением вправо. Поэтому dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + количество конфет в клетке (i,j). В конце, максимальное количество конфет, которое может собрать Сладкоежка, будет равно dp[5][5]. Используя этот алгоритм, мы можем решить задачу следующим образом: python Copy code candies = [ [1, 4, 5, 6, 7], [2, 4, 5, 2, 1], [4, 4, 1, 2, 3], [3, 2, 1, 1, 2], [3, 2, 5, 1, 1] ] dp = [[0]*5 for i in range(5)] # заполняем первую строку и первый столбец dp[0][0] = candies[0][0] for j in range(1, 5): dp[0][j] = dp[0][j-1] + candies[0][j] for i in range(1, 5): dp[i][0] = dp[i-1][0] + candies[i][0] # заполняем оставшуюся часть матрицы for i in range(1, 5): for j in range(1, 5): dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + candies[i][j] # выводим результат print(dp[4][4]) Ответ: 39