Сложность: medium
Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.
Пример:
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
👨💻 Алгоритм:
1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш.
2⃣Итерируйтесь от 1 до n, вычисляя максимальное количество 'A' для каждой позиции, учитывая возможность вставки скопированного текста.
3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш.
😎 Решение:
function maxA($n) {
$dp = array_fill(0, $n + 1, 0);
for ($i = 1; $i <= $n; $i++) {
$dp[$i] = $dp[$i - 1] + 1;
for ($j = 2; $j < $i; $j++) {
$dp[$i] = max($dp[$i], $dp[$j - 2] * ($i - $j + 1));
}
}
return $dp[$n];
}Ставь 👍 и забирай 📚 Базу знаний