K-я лексикографически наименьшая двоичная строка с A 0 и B 1

Даны три положительных целых числа A , B и K. Задача состоит в том, чтобы найти K ^-ю лексикографически наименьшую двоичную строку, содержащую ровно A единиц нулей и B единиц .

Пример:

Input: A = 2, B = 2, K = 4
Output: 1001
Explanation: The lexicographic order of the strings is 0011, 0101, 0110, 1001.

Input: A = 3, B = 3, K = 7
Output: 010110

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

• Инициализируйте 2D-массив dp[][] таким образом, чтобы dp[i][j] обозначало общее количество двоичных строк с i числом 0 и j числом 1 .
• Все значения таблицы dp изначально заполнены нулями, кроме dp[0][0] = 1 , что означает пустую строку.
• Теперь dp[i][j] можно рассчитать как сумму общего количества строк, оканчивающихся на 0 (используя состояние dp как dp[i – 1][j] ), и строки, оканчивающейся на 1 (используя dp состояние как dp[i][j – 1] ). Итак, текущее состояние dp вычисляется как dp[i][j] = dp[i – 1][j] + dp[i][j – 1] .
• После заполнения этой таблицы dp можно использовать рекурсивную функцию для вычисления K ^-й лексикографически наименьшей двоичной строки.
• Итак, определите функцию KthString с параметрами A, B, K и dp .
• Теперь при каждом вызове этой рекурсивной функции:
  • Если значение dp[A][B] не меньше K , то только '0' может присутствовать в этой позиции в K-й лексикографически наименьшей двоичной строке, а затем рекурсивно вызывать функцию для состояния (A – 1, B) .
  • Еще здесь присутствует '1' и рекурсивно вызывается функция для состояния (A, B – 1) .
• Выведите ответ в соответствии с приведенным выше наблюдением.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(A*B)
Вспомогательное пространство: O(A*B)