Метод чисел замыкания для решения проблемы с круглыми скобками

Question

Стандартный вопрос «Сгенерировать скобки» для Leetcode выглядит следующим образом:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

На вкладке решения они объяснили Метод чисел замыкания , который, как мне кажется, трудно понять.

Я сделал пробный прогон кода и даже получил правильный ответ, но не могу понять, почему он работает?Какова интуиция этого метода?

Любая помощь будет принята с благодарностью!

Answer 1

Номер закрытия последовательности в размере наименьшего префикса последовательности, который сам по себе является допустимой последовательностью. Если последовательность имеет закрывающее число k, то вы знаете, что в индексе 0 есть '(', а в индексе k есть ')' Метод решает проблему, проверяя все возможные размеры такого префикса, для каждого он разбивает последовательность на префикс (удаляя элемент 0 и k) и все остальное в последовательности и рекурсивно решая две подзадачи.

Answer 2

Основная идея этого алгоритма - динамическое программирование .Поэтому вы пытаетесь разделить вашу проблему на более мелкие проблемы, которые легко решить .В этом примере вы делаете подзадачи настолько маленькими, что решением является либо пустая строка (если размер равен 0), либо решение «()» (для размера 1).

Вы начинаете использоватьзнание того, что если вам нужна скобка заданной длины, тогда первым символом должен быть "(", а в каком-то более позднем месте строки должен быть этот символ: ")" .В противном случае выходные данные недействительны.

Теперь вы не знаете позицию закрывающей скобки, поэтому просто попробуйте каждую позицию ( первая для цикла ).

Второе, что вы знаете, это то, что между открывающей и закрывающей скобками и после закрывающей скобки должно быть что-то, что вы на самом деле не знаете, как это выглядит (потому что есть много возможностей), но имеетчтобы снова быть допустимой парой скобок .

Теперь эта проблема как раз та проблема, которую вы уже решили .Таким образом, вы просто вводите каждую возможность допустимых скобок (используя меньший размер ввода).Поскольку это именно то, что ваш алгоритм уже делает, вы можете использовать для этого рекурсивный вызов функции.

Итак, подведем итог : вы знаете часть проблемы, а остальная часть проблемыэто точно такая же проблема с меньшим размером.Таким образом, вы решаете небольшую часть проблемы, которую вы знаете, и рекурсивно вызываете тот же метод, чтобы сделать это для остальной части проблемы.После этого вы просто складываете все вместе и получаете свое решение.

Динамическое программирование обычно не так легко понять, но очень эффективно.Так что не беспокойтесь, если вы не понимаете это напрямую.Решать подобные головоломки - лучший способ научиться динамическому программированию.