#arrays #algorithm #dynamic-programming #recursive-type
#массивы #алгоритм #динамическое программирование #рекурсивный тип
Вопрос:
Учитывая два массива (a, b, содержащих только 2 десятичных значения), мы можем либо переместить.
i значение или i-значение. Где value — это элемент с этим индексом в этом массиве.
Нам нужно добраться до последнего элемента, пройдя по каждому элементу только один раз, и мы начинаем с 1-го элемента.
Теперь, как мы можем найти подмножество значений для обмена между a и b, чтобы мы могли достичь последнего индекса.
например, a = 112 b = 212 здесь оба могут дойти до конца, так что пустой набор тоже подойдет. Любого другого набора там нет, который подойдет. Таким образом, ans будет только : {}.
Пример 2: a= 2211 b = 1111. Здесь обе строки могут повторяться и достигать последнего элемента. Теперь, если я заменю (1,2) индексы в a и b, то есть теперь a = 1111 и b = 2211, обе строки все еще могут дойти до конца. Аналогичным образом мы также можем заменить {3},{4},{3,4} и мы все равно можем перейти к последнему индексу в обеих строках.
Итак , есть ли алгоритм для этого ? Как мы можем узнать эти подмножества ? Может быть, решение dp? Я был бы благодарен, если кто-нибудь сможет провести меня по коду, если это возможно.
Комментарии:
1. Можете ли вы привести пример, когда результирующее подмножество не равно нулю?
2. a = 2211 b = 1111 у этого будет много подмножеств, таких как {1,2} , {1,2,4},{3} и так далее.
3. Формулировка проблемы неясна. Насколько я понимаю, пример в вопросе содержит 8 возможных ответов, и каждый из этих ответов должен сработать.
4. @user3386109 можете ли вы, пожалуйста, рассказать мне ответ, на который вы наткнулись?
5. @ShashwatKumar Я привел еще один пример. Проверьте это.