n башен, высота башни i — heights[i]. Вы на башне 0 и хотите попасть на последнюю, n - 1, прыгая только вперёд.
С башни i можно прыгнуть на башню j > i в одном из двух случаев:
- heights[i] ≤ heights[j], и все башни строго между ними ниже heights[i];
- heights[i] > heights[j], и все башни строго между ними не ниже heights[i].
Приземление на башню j стоит fees[j]. Верните минимальную суммарную стоимость пути до последней башни (за стартовую башню платить не нужно).heights=[4, 1, 3, 5], fees=[0, 2, 6, 3] → 3
С башни 0 (высота 4) можно сразу прыгнуть на башню 3 (высота 5): обе башни между ними ниже 4. Это стоит 3. Путь 0 → 1 → 2 → 3 обошёлся бы в 2 + 6 + 3 = 11, а на башню 2 с башни 0 прыгнуть нельзя.
heights=[2, 2, 2], fees=[5, 1, 4] → 5
С башни 0 на башню 2 прыгнуть нельзя: между ними башня такой же высоты, а не ниже. Остаётся путь 0 → 1 → 2 за 1 + 4 = 5. Плата за стартовую башню не берётся.
heights=[7], fees=[9] → 0
heights=[4, 1, 3, 5], fees=[0, 2, 6, 3]
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 118 тестов на сервере, включая скрытые.