Это сообщение в блоге предназначено для пользователей, стремящихся понять альтернативный подход к данной проблеме:
Для тех, кто не пытался ответить на этот вопрос, не стесняйтесь разработать подход к нему. У меня для тебя есть еще одна проблема, если ты решил ее грубой силой.
Хорошо, давай поговорим об этом !! Приведенные ограничения задачи слишком низкие - можно легко придумать решение грубой силы. В любом случае, насколько плохой может быть сложность - O (¹⁰⁰ C ₃), которая имеет порядок O (10⁵) 😜. Но, если ни одна из цифр не порядка 10⁵, каков был бы ваш подход? Кроме того, если кто-то задаст тот же вопрос с делимостью на 7 с ограничением цифр 10⁵ ?? 😮
Решение грубой силы:
Найдите, если существует 1, 2 или 3 цифры, которые делятся на 8. Это можно сделать, написав цикл for 1,2,3 раза подряд. Плохой подход😐
Что ж, теперь нам нужно динамическое программирование (DP) для решения этих задач с более высокими границами .. Хорошо, сначала первый шаг, каким должно быть состояние DP ??
Немного подумав, вы могли бы сформулировать состояние dp как dp [i] [j]:
dp [i] [j] истинно, если можно удалить часть цифр (или ни одной) из первых i цифр, а затем вычислить значение числа, образованного оставшимися цифрами по модулю 8, и получится j ( 0≤j ‹8).
Если это невозможно, то dp [i] [j] будет ложным.
Итак, что такое переходы состояний ??
Как состояние первых элементов «i» зависит от состояния первых элементов «i-1» ?? Эта часть требует хороших размышлений. Теперь предположим, что вы хотите вычислить dp [i] [j], вам нужно сосредоточиться на цифре i ᵗʰ. У этой цифры есть 2 случая -
- Мы можем включить его в наш ответ🤩, ИЛИ
- Мы не можем😋
Для первого случая (1):
Для j: = 0; j ‹8:
dp[i][(j*10+a ᵢ)%8] = (dp[i-1][j] || dp[i][(j*10+a ᵢ)%8] );
Почему?? Видите ли, если для заданных i, j, если dp [i-1] [j] истинно, это означает, что после включения общее (j * 10 + a) по модулю 8 также будет истинным. Почему j * 10 ?? Поскольку мы переместили на одну цифру вперед (добавили еще одну цифру), поэтому начальное число будет умножено на 10. Теперь dp [i] [(j * 10 + a ᵢ)% 8] также может быть истинным в других случаях. Например: для значений a = 3 и j от 0 до 7 имеем:
j …….(j*10+3)%8
0 3
1 5
2 7
3 1
4 3
5 5
6 7
7 1
У нас повторяется 3, 5, 7, 1, и это верно для любого значения aᵢ: первые четыре значения повторяются снова. Итак, если dp [i] [(j * 10 + a ᵢ)% 8] истинно для j = 0, при повторении, когда j = 4, мы обнаруживаем состояние, для которого мы уже вычислили значение. Таким образом, u может также выбрать итерацию j только от 0 до 3.
Теперь наступает часть, в которой мы решаем не включать цифру. В этом случае,
dp[i][(j*10)%8] = (dp[i-1][j] || dp[i][(j*10)%8])
Объяснение такое же, как и раньше: без включения только ai. Наконец, выясните, истинно ли какое-либо из dp [i] [0] для 1≤i≤n. Если это правда, то мы получили число из начальных цифр, которое делится на 8. Иначе, сколько бы цифр мы ни удалили, мы не получим число, делимое на 8.
Этот тип проблем попадает в категорию цифровых DP. Но это общий подход.
Подождите, мы не говорили о базовом случае !! Итак, dp [1] [a ᵢ% 8] = true, иначе dp [1] [j] = false (для j! = A ᵢ% 8). При этом мы получаем линейную сложность с точки зрения количества цифр - O (n * 8), что очень оптимально по сравнению с исходным решением грубой силы.
Если вы обнаружите какую-либо ошибку в блоге или хотите предложить какие-либо правки / подходы, мы более чем приветствуем !! 😃
Ваше здоровье!! Удачного Решению проблемы !!!!
