Ступенькималенькие шаги каждый день

ИНФОРМАТИКА: НАВЫКИ ДЛЯ ЕГЭ

Динамическое программирование

Три примера с разбором по шагам: от простого к сложному. Решите сами и проверьте ответ, регистрация не нужна.

Пример 1

Робот идёт из верхней левой клетки в нижнюю правую, только вправо или вниз, собирая числа во всех посещённых клетках. Строки таблицы: 1, 1, 9; 3, 7, 8; 1, 9, 6. Какова максимальная сумма?

Показать разбор
  1. В каждой клетке M = её число + max(M сверху, M слева).
  2. Таблица максимумов: [1, 2, 11]; [4, 11, 19]; [5, 20, 26].
  3. Итог: 26.
  4. Ответ: 26.

Пример 2

Робот идёт из верхней левой клетки в нижнюю правую, только вправо или вниз, собирая числа во всех посещённых клетках. Строки таблицы: 1, 7, 7; 3, 1, 9; 4, 4, 1. Какова максимальная сумма?

Показать разбор
  1. В каждой клетке M = её число + max(M сверху, M слева).
  2. Таблица максимумов: [1, 8, 15]; [4, 9, 24]; [8, 13, 25].
  3. Итог: 25.
  4. Ответ: 25.

Пример 3

Робот идёт из верхней левой клетки в нижнюю правую, только вправо или вниз, собирая числа во всех посещённых клетках. Строки таблицы: 7, 6, 2; 6, 8, 2; 3, 6, 6. Какова максимальная сумма?

Показать разбор
  1. В каждой клетке M = её число + max(M сверху, M слева).
  2. Таблица максимумов: [7, 13, 15]; [13, 21, 23]; [16, 27, 33].
  3. Итог: 33.
  4. Ответ: 33.

Закрепить тему можно за 20 минут в день

В кабинете ребёнок получает свой вариант заданий по выбранным темам и разбор после сдачи, а вы видите прогресс.

Попробовать 7 дней бесплатно

Другие темы

Нашли ошибку в задаче? Напишите нам.