Рекурсия. Рекурсия с мемоизацией.

@Nik Golor · Регистрация: 07.01.2017

Студворк — интернет-сервис помощи студентам

Добрый день. Задача такова: У нас есть массив для длины строки (пусть будет M=20). У нас есть некие длины слов (колличество не важно пусть будет 50 слов, задаим длины, как значение "j", ну а сами слова пусть будут "i"). Смысл в том, что заполнить словами строки + с учетом пробела + еще штрафы (штрафы - место оставшееся в строке куда не влезло слово и перенесли на след. строку). С этим всё более менее понятно. Но вот тут, момент который мне не понятен следкует. Дойдя до последней строчки, мы получим последний штраф, как мне сказали, его для рекурсии, нужно возвести в куб (^3 для большей наглядности) и пустить на подсчет выше по строкам, мол далее он сам всё сделает, все подсчеты "нужно довериться". Я НЕ ПОНИМАЮ! Как это и зачем, и как это сделать! Говорили, что нужно два цикла, один (внешний) на подсчет всех слов зачем-то, а второй (внутренний) , как я понял должен выполнять (что-то) и условие на пока не >0. Это рекурсия. И я не привык к такому ужасу, не могу понять. Помогите пожалста, а то уже голову сломал. Главное с рекурсией разобраться, а мемоизация, как я понял - это тоже самое, только с сохранением значений пройденный путей.

@Nik Golor · 08.06.2019, 20:38 **[ТС]**

Если кто чем может помочь, прошу помощи. Ибо сроки поджимают, а информацию рою битый день, но безуспешно. Даже примеров нет для самообразования подходящих.

Рыжий Лис · 09.06.2019, 08:30

Фибоначи

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def mem(func):
    def wrap(n):
        if n in wrap._cache:
            r = wrap._cache[n]
            print('HIT  CACHE func(%d) = %d' % (n, r))
        else:
            r = func(n)
            wrap._cache[n] = r
            print('MISS CACHE func(%d) = %d' % (n, r))
        return r
 
    wrap._cache = {}
    return wrap
 
 
@mem
def fib(n):
    return fib(n - 1) + fib(n - 2) if n > 2 else 1
 
print(fib(10))
print(fib._cache)

Добавлено через 4 минуты
Или взять готовый декоратор:

Python
1
2
3
4
5
6
7
8
from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):
    return fib(n - 1) + fib(n - 2) if n > 2 else 1
 
print(fib(10))
print(fib.cache_info())

@Nik Golor · 09.06.2019, 08:55 **[ТС]**

Рыжий Лис, ну тут обсалютно другое, фибо и подобное уже изучил когда начальные знания по рекурсии получал самообразованием. Но увы это тут не особо уместно. Но всё равно спасибо.

@Nik Golor · 10.06.2019, 07:31 **[ТС]**

Как понял, работа осуществляется как в Microsoft Word документе. В принципе распределение слов не проблема. Но вот выполнение рекурсии и рекурсии с мемоизацией по штрафам, и смысл не понятен, и как делать примерных заданий даже нет. Через 2 цикла, да еще и формулой возведения в куб.

@dondublon · 10.06.2019, 12:14

Nik Golor, прочитайте сами ваш первый пост и подумайте, сможет ли его понять посторонний человек.

@Nik Golor · 12.06.2019, 06:15 **[ТС]**

dondublon, если бы было просто, сделал бы сам. А я почти слово в слово всё передал. Ни кто, кто был рядом тоже не понял, задания озвученного мне. Если бы было всё понятно, то даже не сунулся сюда. А сюда люди идут уже от безвыходности, когда не удаётся найти информацию на протяжении недели, как в моём случае. Или не удаётся понять.

@0x10 · 12.06.2019, 07:27

Nik Golor, немного оффтопа.

Не по теме:

У нас две темы с одинаковым содержимым. Невнятно сформулированная задача и непонимание, как ее решать. Причем большую часть тем занимают жалобы на преподавателей, которые не могут сформулировать задачу или замечания к вашему решению. Я допускаю, что все это имеет место быть. Если у вас нет письменного ТЗ, то неудивительно, что до нас вы доносите этот сумбур. Но жалобы не помогут решению задачи. Либо вы будете продолжать панически перебирать решения, либо сядете и спокойно разберетесь в том, что нужно сделать. Второе кажется дольше, на практике оказывается продуктивнее.

С этого момента я предлагаю обсуждать задачу, а не ваше недовольство преподавателями. Последовательно, небольшими шагами. Забыли про «два цикла», «рекурсию» и «мемоизацию». Начнем с вопросов об интуитивном понимании задачи.

Сообщение от Nik Golor

Как понял, работа осуществляется как в Microsoft Word документе

При чем тут текстовый процессор? Почему не обычный текстовый редактор? Объясните.

Сообщение от Nik Golor

В принципе распределение слов не проблема.

Ок. Объясните, как вы решали бы эту задачу. Лучше даже рабочим кодом. Без привязки к методу решения, как сами понимаете.

@dondublon · 12.06.2019, 10:35

Nik Golor, м-да, тяжелый случай.
Прочитайте мою подпись. Вы не умеете грамотно говорить, выражать свои мысли, ставить вопросы. А без этого вам никакой форум не поможет.

@Nik Golor · 13.06.2019, 11:15 **[ТС]**

0x10, вот пример, только надо с циклами работу наладить + не то что выше передали. Я не виноват, как сформулирован пример. Как дали, так и взял, и всем без интереса, пойму я его или нет.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N = 20
l = [10, 15, 2]
 
def f(i):
    if i == 0:
        return (N - l[i])**3
    else:
        m = N - l[i]
        ff = f(i-1) + m**3
        while m >= 0 and i > 2:
            if (m - l[i-1] - 1) > 0:
                m = (m - l[i-1] - 1)
                ff = f(i-2) + m**3
            if (m - l[i-2] - 1) > 0 and i > 3:
               m = m - l[i-2] - 1
               ff = min(ff, m**3 + f(i - 3))
        return ff
print(f(2))

@0x10 · 13.06.2019, 17:58

Сообщение от Nik Golor

только надо с циклами работу наладить

Это нисколько не конкретизирует задачу. Так не разберетесь. Вы понимаете, что именно делает этот код? Что возвращает функция f? Что хранится в ff? Что такое m? Чего не хватает в этом коде?

Я же не просто так начал с примитивных вопросов. Пока вы только перебираете готовые решения.

@Nik Golor · 13.06.2019, 18:36 **[ТС]**

0x10, я могу расписать где что значит. и кстати, выпытал задание совершенно у левого препода. оказывается оно имеет вид такой. Реализовать динамику, рекурсию, рекурсию с мемоизацией.

@0x10 · 13.06.2019, 20:02

Сообщение от Nik Golor

я могу расписать где что значит

Так распишите. Я жду, когда вы начнете излагать свои мысли по поводу задачи.

Покажите результат работы на таком примере: длина строки = 10, текст «aaaaaaa bb cccccc ddddd». Приведите несколько вариантов решений, выберите среди них оптимальный. Распишите, почему он оптимальный. Тогда можно будет говорить о том, что вы понимаете задачу и переходить к методу решения.

IGPIGP · 13.06.2019, 20:06

Сообщение от Nik Golor

0x10, я могу расписать где что значит. и кстати, выпытал задание совершенно у левого препода. оказывается оно имеет вид такой. Реализовать динамику, рекурсию, рекурсию с мемоизацией.

Nik Golor, осталось набраться терпения и набрать текст в пост - слово-в-слово, без лирики. Это испытание, да. Но оно может воодушевить кого-то сделать аналогичные усилия и помочь вам.

@Nik Golor · 13.06.2019, 20:13 **[ТС]**

0x10, N - длинна строки / l - длина слова / ff = f(i-1) + m**3 сама формула распределения / m - это остаток свободный в строке
while m >= 0 and i > 2: пока он не 0 / i - это Номер слова /
if (m - l[i-1] - 1) > 0:
m = (m - l[i-1] - 1)
ff = f(i-2) + m**3
пока остаток - "слово" - 1(пробел как я понял )> 0
m выполняем
а ff - это Штраф с первой по нашу строку
m**3 плюс другие штрафы
if (m - l[i-2] - 1) > 0 and i > 3:
m = m - l[i-2] - 1
ff = min(ff, m**3 + f(i - 3))
return ff
пока (остаток в строке -штраф -пробел)>0 и номер слова >3
остаток в строке = остаток - штрафы суммарные в строке - пробел
суммарные штрафы = минимум min(ff, m**3 + f(i - 3))

Выбор минимального штрафа
Куда лучше последнее слово отправить
возвращаем суммарные штрафы
минимум min(ff, m**3 + f(i - 3))

С текущей строчки
На ней оставить или на строчку вверх

print(f(2)) а это выводим все штрафы в кс

Добавлено через 2 минуты
0x10, на мой код преподаватель сказал. цитирую:
он только сказал, что надо сделать 2 цикла, внешний будет считать число слов общее, а внутренний отцеплять по одному слову.
вот такое, у нас есть два цикла.
первый while мы орентируем как внешний цикл (для подсчета слов) (ранг как я понял тут рпименяем) , а второй while у нас идет как внутренний он для длин слов кароче. + во внутреннем цикле надо реализовать "пока" по оставшемуся свободному месту пока оно есть, что бы выполнялся.
вот такие были наставления по программе.

Добавлено через 49 секунд
рад, что отозвались помочь, хоть кто-то.

@0x10 · 13.06.2019, 20:25

Окей, что лично меня напрягает в этом коде.

Первое.

Сообщение от Nik Golor

while m >= 0 and i > 2

Здесь двойка — это номер последнего слова? Т.е. алгоритм в принципе работает только для последовательности из трех слов?

Второе. Если ff — это штраф за размещение слов c i по j в одной строке, то в этом коде он вычисляется многократно, каждый раз. Ну или как минимум вычисление этих штрафов смешано с поиском оптимального решения. Это выглядит как оптимизация по памяти хранения штрафов.

Мне кажется, если вынести вычисление штрафов и смириться с неоптимальным по памяти способом хранения, то алгоритм станет проще.

Короче, этап первый, шаги.

1. Входные данные. Для наглядности пусть исходными данными будет текст. Текст легко разделить на список слов, метод split в помощь. Далее по списку слов легко сформировать список длин этих слов.

2. Создадим матрицу штрафов. Только назовем ее не ff, а costs, чтобы потом не вспоминать.
2.1 Создать матрицу размерности len(words)×len(words).
2.2 Заполнить все ячейки матрицы бесконечностями. math.inf подойдет.
2.3 Заполнить ячейки по правилу: если слова c i по j включительно умещаются в строке, то в ячейку costs[i][j] записать штраф для такого размещения. Примечание: для вычисления нам будет полезна вспомогательная функция calc_cost(words_lens, line_len), которая принимает список длин слов с i по j и максимальную длину строки и возвращает штраф. В вашем коде эта формула дублируется в нескольких местах, не надо так.

Когда сформируете матрицу штрафов, вычислите ее для какого-нибудь примера вручную, сравните результаты. Потом можно будет посмотреть на получившийся код и обрести некоторую часть просветления. После этого можно будет двигаться дальше.

@Nik Golor · 13.06.2019, 20:34 **[ТС]**

Рекурсия. Рекурсия с мемоизацией. (полная версия в печатном варианте, работа со строками)
Входной текст состоит из слов с известными длинами (количеством символов) I1,I2, ..., In и представляет
абзац. Его нужно "правильно отформировать" и вывести в несколько сток длинной M символов (M>=max Ii).
Форматирование заключается в следующем. Если в строке размещаются слова с i-го по j-е, то между ними
вставляется по одному пробелу и вычисляется остаток M j+i-(Ii+...Ij), который должен быть неотрецательным.
Нужно минимизировать сумму кубов остатков по всем строкам, кроме последней.
Ввод: Первая строка входного файла содержит число слов n и длину строки M. Вторая строка содержит
длины I[1],I[2],...,I[n].
Вывод: минимум суммы кубов остатков по всем строкам, кроме последней.
Структура решения - построчно в формате "индекс первого слова - индекс второго слова" расположенная разбивка
текста на строки.

Добавлено через 2 минуты

Сообщение от 0x10

Здесь двойка — это номер последнего слова? Т.е. алгоритм в принципе работает только для последовательности из трех слов?

согласен, это ошибка.

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

Сообщение от 0x10

Короче, этап первый, шаги.
1. Входные данные. Для наглядности пусть исходными данными будет текст. Текст легко разделить на список слов, метод split в помощь. Далее по списку слов легко сформировать список длин этих слов.
2. Создадим матрицу штрафов. Только назовем ее не ff, а costs, чтобы потом не вспоминать.
2.1 Создать матрицу размерности len(words)×len(words).
2.2 Заполнить все ячейки матрицы бесконечностями. math.inf подойдет.
2.3 Заполнить ячейки по правилу: если слова c i по j включительно умещаются в строке, то в ячейку costs[i][j] записать штраф для такого размещения. Примечание: для вычисления нам будет полезна вспомогательная функция calc_cost(words_lens, line_len), которая принимает список длин слов с i по j и максимальную длину строки и возвращает штраф. В вашем коде эта формула дублируется в нескольких местах, не надо так.

@0x10 · 13.06.2019, 20:37

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

Сообщение от Nik Golor

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

Конкретно эта часть простая.

@Nik Golor · 13.06.2019, 20:55 **[ТС]**

Сообщение от 0x10

Конкретно эта часть простая.

пока что мало опыта, но я попробую справиться.

@0x10 · 13.06.2019, 21:08

Пока первый этап не готов, забегу чуть вперед.

Этап 2: поиск оптимального решения.
Вот этот этап сложно комментировать. Просто потому что есть рекуррентная формула, которую нужно взять и аккуратно запрограммировать. В вашем коде это уже есть, но я его не проверял. Перепишу соотношение с учетом того, что мы нумеруем слова с нуля.

$https://www.cyberforum.ru/cgi-bin/latex.cgi?optimal\_cost(j) = \left\{\begin{matrix}0, & j = -1 \\ min(optimal\_cost(i - 1) + costs[i, j]) & i = \bar{0, j} \end{matrix}\right.$

Здесь:
- optimal_cost(j) — функция вычисления штрафа за оптимальное расположение слов с 0 по j.
- costs - матрица штрафов, вычисленная на этапе 1.

Обратите внимание, что минимальный штраф вычисляется относительно всех предыдущих слов.

Рекомендация: лучше использовать не функцию min, а написать условие со сравнением. Нам в него потом еще втыкать сохранение результата.

В результате этого этапа у нас будет вычислен штраф для оптимального способа форматирования текста. Время остановиться, прорешать вручную, сравнить результаты.

Этап 3: сохранение результата.
Мало вычислить штраф для оптимального решения, нужно еще запоминать, какие конкретно слова мы использовали для его получения. Заводим список result, размер списка == количество слов. На предыдущем этапе у нас есть точка расширения: условие проверки, является ли решение для j слов с использованием i-того слова оптимальным. Вот и сохраняем result[j] = i. Я тут плохо объясняю на словах, но если весь код будет написан аккуратно, то там будет очевидно, что и куда воткнуть. Просто других подходящих мест не останется.

Этап 4: вывод результата.
Если честно, мне уже лень расписывать, какая структура данных получается в результате сохранения результата, и как с ней работать. Я уже кидал ссылку на готовое решение: https://www.geeksforgeeks.org/... lem-dp-19/. Там есть функция printSolution. Можно взять и немного изменить под свои потребности. Входная структура данных та же самая.

Этап 5: мемоизация.
Ну здесь халява. Заводим список, по размеру равный количеству слов. Заполняем бесконечностями. Когда вычислили штраф за оптимальное форматирование слов [0; j], в j-тый элемент массива записали этот штраф. В функции вычисления оптимального штрафа (optimal_cost) перед всеми вычислениями нужно сначала проверить: есть ли уже вычисленный результат в j-той ячейке. Если есть — вернуть его, и ничего больше не вычислять.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Nik Golor 3 / 3 / 0 Регистрация: 07.01.2017 Сообщений: 101

	Рекурсия. Рекурсия с мемоизацией. 08.06.2019, 09:48. Показов 6106. Ответов 62 Метки нет (Все метки) Добрый день. Задача такова: У нас есть массив для длины строки (пусть будет M=20). У нас есть некие длины слов (колличество не важно пусть будет 50 слов, задаим длины, как значение "j", ну а сами слова пусть будут "i"). Смысл в том, что заполнить словами строки + с учетом пробела + еще штрафы (штрафы - место оставшееся в строке куда не влезло слово и перенесли на след. строку). С этим всё более менее понятно. Но вот тут, момент который мне не понятен следкует. Дойдя до последней строчки, мы получим последний штраф, как мне сказали, его для рекурсии, нужно возвести в куб (^3 для большей наглядности) и пустить на подсчет выше по строкам, мол далее он сам всё сделает, все подсчеты "нужно довериться". Я НЕ ПОНИМАЮ! Как это и зачем, и как это сделать! Говорили, что нужно два цикла, один (внешний) на подсчет всех слов зачем-то, а второй (внутренний) , как я понял должен выполнять (что-то) и условие на пока не >0. Это рекурсия. И я не привык к такому ужасу, не могу понять. Помогите пожалста, а то уже голову сломал. Главное с рекурсией разобраться, а мемоизация, как я понял - это тоже самое, только с сохранением значений пройденный путей. 0

@Nik Golor 3 / 3 / 0 Регистрация: 07.01.2017 Сообщений: 101
	08.06.2019, 20:38 [ТС]
	Если кто чем может помочь, прошу помощи. Ибо сроки поджимают, а информацию рою битый день, но безуспешно. Даже примеров нет для самообразования подходящих. 0

@Nik Golor 3 / 3 / 0 Регистрация: 07.01.2017 Сообщений: 101
	09.06.2019, 08:55 [ТС]
	Рыжий Лис, ну тут обсалютно другое, фибо и подобное уже изучил когда начальные знания по рекурсии получал самообразованием. Но увы это тут не особо уместно. Но всё равно спасибо. 0

@Nik Golor 3 / 3 / 0 Регистрация: 07.01.2017 Сообщений: 101
	10.06.2019, 07:31 [ТС]
	Как понял, работа осуществляется как в Microsoft Word документе. В принципе распределение слов не проблема. Но вот выполнение рекурсии и рекурсии с мемоизацией по штрафам, и смысл не понятен, и как делать примерных заданий даже нет. Через 2 цикла, да еще и формулой возведения в куб. 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	10.06.2019, 12:14
	Nik Golor, прочитайте сами ваш первый пост и подумайте, сможет ли его понять посторонний человек. 2

@Nik Golor 3 / 3 / 0 Регистрация: 07.01.2017 Сообщений: 101
	12.06.2019, 06:15 [ТС]
	dondublon, если бы было просто, сделал бы сам. А я почти слово в слово всё передал. Ни кто, кто был рядом тоже не понял, задания озвученного мне. Если бы было всё понятно, то даже не сунулся сюда. А сюда люди идут уже от безвыходности, когда не удаётся найти информацию на протяжении недели, как в моём случае. Или не удаётся понять. 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	12.06.2019, 10:35
	Nik Golor, м-да, тяжелый случай. Прочитайте мою подпись. Вы не умеете грамотно говорить, выражать свои мысли, ставить вопросы. А без этого вам никакой форум не поможет. 2

@Nik Golor 3 / 3 / 0 Регистрация: 07.01.2017 Сообщений: 101
	13.06.2019, 18:36 [ТС]
	0x10, я могу расписать где что значит. и кстати, выпытал задание совершенно у левого препода. оказывается оно имеет вид такой. Реализовать динамику, рекурсию, рекурсию с мемоизацией. Миниатюры 0

@Nik Golor 3 / 3 / 0 Регистрация: 07.01.2017 Сообщений: 101
	13.06.2019, 20:13 [ТС]
	0x10, N - длинна строки / l - длина слова / ff = f(i-1) + m3 сама формула распределения / m - это остаток свободный в строке while m >= 0 and i > 2: пока он не 0 / i - это Номер слова / if (m - l[i-1] - 1) > 0: m = (m - l[i-1] - 1) ff = f(i-2) + m3 пока остаток - "слово" - 1(пробел как я понял )> 0 m выполняем а ff - это Штраф с первой по нашу строку m3 плюс другие штрафы if (m - l[i-2] - 1) > 0 and i > 3: m = m - l[i-2] - 1 ff = min(ff, m3 + f(i - 3)) return ff пока (остаток в строке -штраф -пробел)>0 и номер слова >3 остаток в строке = остаток - штрафы суммарные в строке - пробел суммарные штрафы = минимум min(ff, m3 + f(i - 3)) Выбор минимального штрафа Куда лучше последнее слово отправить возвращаем суммарные штрафы минимум min(ff, m3 + f(i - 3)) С текущей строчки На ней оставить или на строчку вверх print(f(2)) а это выводим все штрафы в кс Добавлено через 2 минуты 0x10, на мой код преподаватель сказал. цитирую: он только сказал, что надо сделать 2 цикла, внешний будет считать число слов общее, а внутренний отцеплять по одному слову. вот такое, у нас есть два цикла. первый while мы орентируем как внешний цикл (для подсчета слов) (ранг как я понял тут рпименяем) , а второй while у нас идет как внутренний он для длин слов кароче. + во внутреннем цикле надо реализовать "пока" по оставшемуся свободному месту пока оно есть, что бы выполнялся. вот такие были наставления по программе. Добавлено через 49 секунд рад, что отозвались помочь, хоть кто-то. 0

@0x10 3258 / 2060 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	13.06.2019, 21:08
	Пока первый этап не готов, забегу чуть вперед. Этап 2: поиск оптимального решения. Вот этот этап сложно комментировать. Просто потому что есть рекуррентная формула, которую нужно взять и аккуратно запрограммировать. В вашем коде это уже есть, но я его не проверял. Перепишу соотношение с учетом того, что мы нумеруем слова с нуля. $https://www.cyberforum.ru/cgi-bin/latex.cgi?optimal\_cost(j) = \left\{\begin{matrix}0, & j = -1 \\ min(optimal\_cost(i - 1) + costs[i, j]) & i = \bar{0, j} \end{matrix}\right.$ Здесь: - optimal_cost(j) — функция вычисления штрафа за оптимальное расположение слов с 0 по j. - costs - матрица штрафов, вычисленная на этапе 1. Обратите внимание, что минимальный штраф вычисляется относительно всех предыдущих слов. Рекомендация: лучше использовать не функцию min, а написать условие со сравнением. Нам в него потом еще втыкать сохранение результата. В результате этого этапа у нас будет вычислен штраф для оптимального способа форматирования текста. Время остановиться, прорешать вручную, сравнить результаты. Этап 3: сохранение результата. Мало вычислить штраф для оптимального решения, нужно еще запоминать, какие конкретно слова мы использовали для его получения. Заводим список result, размер списка == количество слов. На предыдущем этапе у нас есть точка расширения: условие проверки, является ли решение для j слов с использованием i-того слова оптимальным. Вот и сохраняем result[j] = i. Я тут плохо объясняю на словах, но если весь код будет написан аккуратно, то там будет очевидно, что и куда воткнуть. Просто других подходящих мест не останется. Этап 4: вывод результата. Если честно, мне уже лень расписывать, какая структура данных получается в результате сохранения результата, и как с ней работать. Я уже кидал ссылку на готовое решение: https://www.geeksforgeeks.org/... lem-dp-19/. Там есть функция printSolution. Можно взять и немного изменить под свои потребности. Входная структура данных та же самая. Этап 5: мемоизация. Ну здесь халява. Заводим список, по размеру равный количеству слов. Заполняем бесконечностями. Когда вычислили штраф за оптимальное форматирование слов [0; j], в j-тый элемент массива записали этот штраф. В функции вычисления оптимального штрафа (optimal_cost) перед всеми вычислениями нужно сначала проверить: есть ли уже вычисленный результат в j-той ячейке. Если есть — вернуть его, и ничего больше не вычислять. 0