Сложность: easy
Мы играем в угадайку. Правила игры следующие:
Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.
Пример:
Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.
👨💻 Алгоритм:
1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента.
2⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость.
3⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы.
😎 Решение:
class Solution {
func calculate(_ low: Int, _ high: Int) -> Int {
if low >= high {
return 0
}
var minres = Int.max
for i in low...high {
let res = i + max(calculate(i + 1, high), calculate(low, i - 1))
minres = min(res, minres)
}
return minres
}
func getMoneyAmount(_ n: Int) -> Int {
return calculate(1, n)
}
}Ставь 👍 и забирай 📚 Базу знаний