Всем привет!
Недавно решал задачу, и в решении автор пишет ДП по двум измерениям. DP[i][j] = {на префиксе i, суммарно использовали j мороженого и mooney}. То есть он по сути сжал два измерения в одно. Учитывая что мороженное надо брать жадно то это работает, но решения мне показалось очень неочевидным и похоже на то что это какой-то определенный подход. Хотел спросить реально ли это или автор просто придумал очень геморную задачу) и если это является подходом не могли бы подсказать где можно найти похожие задачи.
1 лайк
Такие задачи где один из параметров ты превращаешь в значение дпшки существуют и это можно назвать подходом.
На зимних республиканских сборах я применил данный подход для решения одной задачи.
Где найти похожие задачи не знаю, @fractal мб помнит
1 лайк