Задача: Смена операции

Условие: дается целое число, нужно переконвертировать данное число в сумму, слагаемых должно быть не менее двух. А само разложение должно осуществляться таким образом, что произведение слагаемых будет максимальным.

В результате необходимо получить это самое произведение.

Пример:

Ввод: n = 2

Вывод: 1

Объяснение: 2 = 1 + 1, 1 × 1 = 1.

Ввод: n = 10

Вывод: 36

Объяснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Решение:

Интуиция

В задаче предлагается разбить целое число n на сумму k положительных целых чисел, где k >= 2, чтобы максимизировать произведение этих чисел. Для решения этой задачи мы можем использовать динамическое программирование.

Ключевым моментом здесь является то, что для максимизации произведения мы должны стремиться разбить целое число на как можно большее число 3, поскольку умножение на 3 дает большее произведение по сравнению с другими целыми числами. Однако при делении n на 3 может получиться остаток, который необходимо правильно обработать.

Подход

Приведем пошаговый подход к решению задачи:

1. Создайте массив dp размера n+1 для хранения максимального произведения для каждого целого числа от 1 до n. Инициализируйте dp[0], dp[1] и dp[2] в 1, так как их нельзя разбить дальше.
2. С помощью вложенного цикла выполните итерацию от i = 3 до n, где i - текущее целое число, которое мы пытаемся разбить.
3. Внутри внутреннего цикла выполните итерацию от j = 1 до i-1, где j представляет собой одну часть текущего целого числа i, а i - j - другую часть.
4. Вычислите произведение j * (i - j), так как оно представляет собой произведение разбиения i на две части, j и i - j.
5. Обновить dp[i] максимальным значением из его текущего значения, j * (i - j) и dp[i - j] * j. Этот шаг учитывает возможность разбиения i более чем на две части путем рассмотрения максимального произведения для оставшейся части i - j и умножения его на j.
6. Наконец, возвращается dp[n], в котором хранится максимальное произведение для заданного целого числа n.

Сложность

Временная сложность: O(n2)  - Имеем вложенный цикл, итерирующий по i от 3 до n и по j от 1 до i-1.

Пространственная сложность: O(n) - Для хранения максимальных произведений мы используем массив размера n+1.

Код:

Python

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1

        for i in range(3, n + 1):
            for j in range(1, i):
                x = j
                y = i - x
                dp[i] = max(dp[i], max(x * y, dp[y] * x))

        return dp[n]