Максимальная сумма очков за K зданий из N этажей с M прыжками

Опубликовано: 21 Сентября, 2022

Даны K зданий с N этажами и стоящий на земле человек, который может совершить не более M прыжков. Человек должен подняться на вершину и набрать максимальное количество очков. Найдите максимальное количество очков, которое можно набрать, если человек сможет либо подняться по лестнице на следующий этаж того же здания, либо перепрыгнуть на следующий этаж любого из соседних зданий.

Пример:

Input: N = 5, M = 2, K = 3, 
points = [ [4, 5, 1, 2, 10], 
[9, 7, 3, 20, 16], 
[ 6, 12, 13, 9, 8] ]
Output: 70
Explanation: Start from building 2. Collect the 9 points in the first floor.
Jump to building 3. Collect the 12 points from the second and 13 points from third floor. (Jump 1)
Jump back to building 2. Collect the 20 points from fourth floor and 16 points in fifth floor. (Jump 2)
Number of jumps made = 2
Number of points collected= 9+12+13+20+16 = 70 points

Input: N = 4, M = 1, K = 3, 
points = [ [7, 5, 4, 10], 
[8, 9, 20, 16], 
[ 12, 13, 3, 8] ]
Output: 61

Подход: Данная проблема может быть решена с помощью динамического программирования:

  • Сначала мы определяем состояние dp
    • состояние dp(i, j, k) – максимальное количество баллов, которое можно набрать, если человек находится на i -м этаже, совершив не более j прыжков и оказавшись в k -м доме
  • Затем мы определим базовые случаи
    • Если есть только один этаж, то человек не может прыгать, поставьте количество очков в этом месте.
    • Если разрешено 0 прыжков, вы можете выбрать одно из трех зданий и продолжить восхождение на то же здание.
    • таким образом, человек может брать баллы только с предыдущего этажа того же здания и добавлять текущие баллы
  • Затем определим переход между состояниями
  • если мы находимся на первом здании, то мы можем:
    • выходи из первого корпуса, этажом ниже, без прыжков
    • прийти из соседнего здания, этажом ниже, добавлен один прыжок
  • добавить очки, хранящиеся в здании 1 на i-м этаже для обоих случаев
  • Если мы находимся в промежуточном здании, то мы можем:
    • прийти из предыдущего здания, на один этаж ниже, добавлен один прыжок
    • прийти из текущего здания, на один этаж ниже, без прыжка
    • может прийти из соседнего здания, на один этаж ниже, добавлен один прыжок
  • добавит очки, хранящиеся в промежуточном здании на 1-м этаже для всех 3-х случаев
  • Если мы находимся в последнем здании, то мы можем:
    • из предыдущего здания, на один этаж ниже, добавлен один прыжок
    • из последнего здания, этажом ниже, прыжок не добавлен
  • добавит очки, хранящиеся в последнем здании на i-м этаже для обоих случаев
  • Для окончательного ответа верните максимальное количество очков, набранных на верхнем этаже всего здания после выполнения допустимого количества прыжков.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M*K), что означает O(этажи*прыжки*здания)
Вспомогательное пространство: O(N*M*K), что означает O(этажи*прыжки*здания)

РЕКОМЕНДУЕМЫЕ СТАТЬИ