Лопающиеся шары
Hard
Есть шары в ряд со значениями
Нужно лопнуть все шары в некотором порядке и набрать максимальную суммарную награду.
nums[i]. Когда вы лопаете шар i, получаете nums[left] * nums[i] * nums[right] очков, где left и right — ближайшие ещё не лопнувшие соседи. За границами ряда стоят виртуальные шары со значением 1.Нужно лопнуть все шары в некотором порядке и набрать максимальную суммарную награду.
Примеры:
Вход:
[3, 1, 5, 8]
Выход:
167
Объяснение: [3,1,5,8]: существует порядок лопания, дающий суммарно 167 очков — это максимум для этого ряда.
Вход:
[1, 5]
Выход:
10
Объяснение: [1,5]: например, сначала лопнуть 1: сосед слева виртуальная 1, справа 5 → 1·1·5 = 5; затем 5 с двумя виртуальными единицами → 1·5·1 = 5; итого 10.
Вход:
[1]
Выход:
1
Объяснение: [1]: единственный шар лопается между двумя виртуальными единицами: 1·1·1 = 1.
Ограничения:
1 <= nums.length <= 300
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!