Сложность: medium
На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.
Пример:
Input: n = 3
Output: 3
👨💻 Алгоритм:
1⃣Используйте динамическое программирование для отслеживания минимального количества операций, необходимых для достижения определенного количества 'A' на экране.
2⃣Итерируйтесь от 1 до n, проверяя все возможные делители текущего числа и обновляя минимальное количество операций для каждого числа.
3⃣Возвращайте значение из таблицы динамического программирования для n.
😎 Решение:
function minSteps($n) {
if ($n == 1) return 0;
$dp = array_fill(0, $n + 1, 0);
for ($i = 2; $i <= $n; $i++) {
$dp[$i] = $i;
for ($j = 1; $j <= $i / 2; $j++) {
if ($i % $j == 0) {
$dp[$i] = min($dp[$i], $dp[$j] + $i / $j);
}
}
}
return $dp[$n];
}Ставь 👍 и забирай 📚 Базу знаний