Всем привет!
В сегодняшней задаче нужно было разбить заданное число n, на некоторую сумму чисел, таким образом, чтобы произведение этих чисел было максимальным.
Первые несколько минут, я конечно же сидел, не понимая как взяться за неё. Прорыв произошел, когда я начал проверять разные числа с помощью тесткейсов в самой оболочке LeetCode. Оказалось, что в данной задаче число «3» поистине обладает магическими свойствами (я даже видел строгое математическое доказательство, почему так происходит, но не вчитывался особо).
В целом, заданное число нужно разбивать на сумму по-максимуму состоящую из троек. Собственно это видно в примерах. Так числа разбиваются на:
10 = 3 + 3 + 4; 3 * 3 * 4 = 36.
11 = 3 + 3 + 3 + 2; 3 * 3 * 3 * 2 = 54
12 = 3 + 3 + 3 + 3; 3 * 3 * 3 * 3 = 81
13 = 3 + 3 + 3 + 4; 3 * 3 * 3 * 4 = 108
Здесь уже видно некоторый патерн, особенно если учесть, что 4 = 2*2.
Собственно, решение было построено на вычитании тройки из заданного числа и одновременного умножения результата на тройку. Это я делал в цикле while.
Как видно, подход вроде простой, но вот описать его коротко и красиво с первого раза не получилось. Кроме вычитания тройки в цикле есть куча условий, которые боролись с крайними случаями. Так для «2» есть только одно возможное разбиение: 2 = 1 + 1 . А для «3» разбиение с максимальным произведением: 3 = 2 + 1. Я не стал заморачиваться и написал их я явном виде.
Но самое сложное было убрать множество условий из самого тела цикла while. Потому что там нужно обрабатывать последние числа в разбиении: случай «4», случай «3» и случай «2» ( в первом решении все эти случаи написаны отдельно).
Я перепробовал кучу вариантов, например такой:
Тут для «2» и «3» используется общее выражение ( максимальное произведение = n - 1). Все условия в цикле сохранены, только несколько скомпонованы. Так «2» и «4» стоят в одном условии с логическим «или». А конечную тройку я все-таки запихнул во все остальные, только теперь условие выглядит сильно корявее (n - 3 >= 0)
Но в самом конце оказалось, что во всех этих случаях, когда остается только последнее число ( «2», «3» или «4»), нужно просто домножить результат на него. То есть цикл стал идти не до нуля (while n > 0:), а до четырех (while n > 4:), а последнее умножение происходит уже вне цикла. Так что из while вообще изчезли все условия.
Итоговый вариант решения получился такой:
Конечно, это не самое эффективное решение. Наиболее эффективно задачу решать методом динамического программирования. Но я это еще не умею…
Что же, пойду дальше решать задачи и изучать Python