Как можно получить результаты разбиения на слагаемые с помощью динамического программирования?

Question

Любим

python , алгоритмы

Как можно получить результаты разбиения на слагаемые с помощью динамического программирования?

Здравствуйте!

У меня есть код, который считает количество разбиений числа на слагаемые. Однако я хочу, чтобы он также печатал сами слагаемые. Как можно это сделать?

Вот имеющийся код:

```python
def partition(n):
    parts = [1]+[0]*n
    for i in range(1, n+1):
        for j in range(i, n+1):
            parts[j] += parts[j-i] 
    return parts[n]
        
print(partition(227))
```

Благодарю!

18 сентября 2023 г. 6:16

Ответы на вопрос 2

Похожие вопросы

Answer 1

Привет!

Чтобы получить результаты разбиения на слагаемые с помощью динамического программирования, вам необходимо внести некоторые изменения в код. Вместо того, чтобы хранить только количество разбиений в каждом шаге, вы можете хранить список списков, где каждый внутренний список будет содержать слагаемые для данной суммы.

Вот измененный код, который печатает все слагаемые:

```python
def partition(n):
    partitions = [[] for _ in range(n+1)]
    partitions[0] = [[]]
    
    for i in range(1, n+1):
        for j in range(i, n+1):
            for prev_partition in partitions[j-i]:
                partitions[j].append(prev_partition + [i])
    
    return partitions[n]
        
result = partition(227)
for partition in result:
    print(partition)
    ```

Теперь код будет печатать все различные слагаемые для заданного числа.

Answer 2

Новая функция должна быть создана для перебора всех разбиений числа. Текущая функция реализует вычисление P(n, n) с использованием рекуррентной формулы.