Три примера с разбором по шагам: от простого к сложному. Решите сами и проверьте ответ, регистрация не нужна.
Пример 1
Робот идёт из верхней левой клетки в нижнюю правую, только вправо или вниз, собирая числа во всех посещённых клетках. Строки таблицы: 1, 1, 9; 3, 7, 8; 1, 9, 6. Какова максимальная сумма?
Показать разбор
В клетку можно прийти только сверху или слева. Поэтому лучшая сумма в клетке — это её число плюс большая из лучших сумм сверху и слева.
Заполняем таблицу лучших сумм по строкам: 1, 2, 11; 4, 11, 19; 5, 20, 26.
В правой нижней клетке получилось 26.
Ответ: 26.
Пример 2
Робот идёт из верхней левой клетки в нижнюю правую, только вправо или вниз, собирая числа во всех посещённых клетках. Строки таблицы: 1, 7, 7, 3; 1, 9, 4, 4; 1, 5, 5, 5. Какова максимальная сумма?
Показать разбор
В клетку можно прийти только сверху или слева. Поэтому лучшая сумма в клетке — это её число плюс большая из лучших сумм сверху и слева.
Заполняем таблицу лучших сумм по строкам: 1, 8, 15, 18; 2, 17, 21, 25; 3, 22, 27, 32.
В правой нижней клетке получилось 32.
Ответ: 32.
Пример 3
Робот идёт из верхней левой клетки в нижнюю правую, только вправо или вниз, собирая числа во всех посещённых клетках. Строки таблицы: 7, 6, 2, 6; 8, 2, 3, 6; 6, 7, 8, 8; 4, 4, 8, 7. Какова максимальная сумма?
Показать разбор
В клетку можно прийти только сверху или слева. Поэтому лучшая сумма в клетке — это её число плюс большая из лучших сумм сверху и слева.
