rr
суть дп же в разбиении на мелкие проблемы и решение их рекурсивно
Size: a a a
2021 April 27
rr
тут более на жадное решение походит
AM
Да - ты прав. Но дп сейчас подразумевается как решение через матрицу - не помню аббревиатуру lca или как-то так
AM
Кстати я проверил - где-то ошибка у меня =(
AM
Типа делят почему-то решение на два вида
AM
рекурсия + мемо или матрица. По сути они однохуйственны - просто в матрице сохраняем результат, а не в хештаблице. Но вот только догадаться до матрицы - это надо быть гением уровнем бог
rr
какая матрица ?
rr
как ты матрицу строишь ?
AM
В данном случае здесь одномерная
AM
ну те не матрица - а просто одномерный массив
AM
Да и тут я неверно решил
AM
ща поищу ошибку
rr
в сути тут все решения как вариации можно в дерево вывести
rr
дерево частный случай графа
rr
граф имеет матрицу смежности
rr
так ты строишь матрицы эти ?
S
Да, но для звонков у меня неубиваемая Nokia 1100
AM
Не - вообще не думаю про графы. Думаю о базовом кейсе - а дальше высчитываю dp[i + 1] как отношение предыдущих значений. Сначала я думаю о дереве решений - потом смотрю что повторяется. И пытаюсь придумать как это в дп превратить. Я ж говорю - что не китаец чтобы это делать идеально =))) Это очень сложно
AM
Ща - я попробую дорешать эту задачу. А потом распишу как и что