Добрый вечер!
Можете подсказать по задаче:
Даны n чисел между ними нужно расставить знаки ‘+’ и ‘-‘ так, чтобы получилась заданная сумма.
Перебором не подходит, при n = 50 уже не выполнимо.
Задача из раздела на динамическое программирование.
Пробовал делать состояние:
Dp[i] достижима ли сумма i , но столкнулся с тем, что состояния получаются при этом топологически не упорядочены, так если для выбирать знак для i ого числа, и мы берём с минусом, то мы приходим из sum + a[i]

а есть ссылка, откуда задача? Тоже хочу сделать

Добрый вечер!
Можете подсказать по задаче:
Даны n чисел между ними нужно расставить знаки ‘+’ и ‘-‘ так, чтобы получилась заданная сумма.
Перебором не подходит, при n = 50 уже не выполнимо.
Задача из раздела на динамическое программирование.
Пробовал делать состояние:
Dp[i] достижима ли сумма i , но столкнулся с тем, что состояния получаются при этом топологически не упорядочены, так если для выбирать знак для i ого числа, и мы берём с минусом, то мы приходим из sum + a[i]

Ну вот данный на вход  и является подходящей строкой, O(1).

Ну мне кажется, что в том сообщениее чего-то не хватает.

Думаю можно замутить что нибудь с бором и так как все строки в нем отсортированы поддерживать range индексов подходящих строк в каждой вершине

Добрый вечер!
Можете подсказать по задаче:
Даны n чисел между ними нужно расставить знаки ‘+’ и ‘-‘ так, чтобы получилась заданная сумма.
Перебором не подходит, при n = 50 уже не выполнимо.
Задача из раздела на динамическое программирование.
Пробовал делать состояние:
Dp[i] достижима ли сумма i , но столкнулся с тем, что состояния получаются при этом топологически не упорядочены, так если для выбирать знак для i ого числа, и мы берём с минусом, то мы приходим из sum + a[i]