Наименьшее n-битное целое число c, которое имеет k 1-бит и является суммой двух n-битных целых чисел, для которых g, h битов установлены в 1 (динамическое программирование)

Я пытаюсь решить следующую проблему:

Найдите наименьшее n-битное целое число c, которое имеет k 1-бит и является суммой двух n-битных целых чисел, для которых g, h битов установлены в 1. g, h, k <= n

Начнем с того, что n-битное целое здесь означает, что мы можем использовать все n биты, то есть макс. значение такого целого числа 2^n - 1, Описанное целое число может вообще не существовать.
Это очевидный случай k > g + h не имеет решений и для g + h = k ответ просто 2^k - 1 (первый k биты 1-битные, k - n нули спереди).

Что касается некоторых примеров того, что программа должна делать:

g = h = k = 4, n = 10 :
0000001111 + 0000001111 = 0000011110
15 + 15 = 30 (30 should be the output)(4, 6, 5, 10):
0000011110 + 0000111111 = 0001011101
30 + 63 = 93

(30, 1, 1, 31):
1 + (2^30 - 1) = 2^30

На мой взгляд, это проблема динамического программирования, и я выбрал следующий подход:
Позволять dp[g][h][k][n][c] быть описанным целым числом и c это необязательный бит для переноски. Я пытаюсь восстановить возможные суммы в зависимости от младших битов.
Так, dp[g][h][k][n + 1][0] это минимум

(0, 0):       dp[g][h][k][n][0]
(0, 0): 2^n + dp[g][h][k - 1][n][1]
(1, 0): 2^n + dp[g - 1][h][k - 1][n][0]
(0, 1): 2^n + dp[g][h - 1][k - 1][n][0]

Так же, dp[g][h][k][n + 1][1] это минимум

(1, 1): dp[g - 1][h - 1][k][n][0]
(1, 1): dp[g - 1][h - 1][k - 1][n][1] + 2^n
(1, 0): dp[g - 1][h][k][n][1]
(0, 1): dp[g][h - 1][k][n][1]

Идея не такая уж сложная, но я не очень разбираюсь в таких вещах, и мой алгоритм не работает даже в самых простых случаях. Я выбрал подход сверху вниз. Мне сложно рассмотреть все угловые случаи. Я действительно не знаю, правильно ли я выбрал базу рекурсии и т. Д. Мой алгоритм даже не работает для самого основного случая для g = h = k = 1, n = 2(ответ 01 + 01 = 10). Там не должно быть ответа на g = h = k = 1, n = 1 но алгоритм дает 1(именно поэтому в первом примере выводятся 1 вместо 2).
Итак, вот мой ужасный код (только очень простой C ++):

int solve(int g, int h, int k, int n, int c = 0) {
if (n <= 0) {
return 0;
}
if (dp[g][h][k][n][c]) {
return dp[g][h][k][n][c];
}
if (!c) {
if (g + h == k) {
return dp[g][h][k][n][c] = (1 << k) - 1;
}
int min, a1, a2, a3, a4;
min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
if (g + h > k && k <= n - 1) {
a1 = solve(g, h, k, n - 1, 0);
}
if (g + h >= k - 1 && k - 1 <= n - 1) {
a2 = (1 << (n - 1)) + solve(g, h, k - 1, n - 1, 1);
}
if (g - 1 + h >= k - 1 && k - 1 <= n - 1) {
a3 = (1 << (n - 1)) + solve(g - 1, h, k - 1, n - 1, 0);
}
if (g + h - 1 >= k - 1 && k - 1 <= n - 1) {
a4 = (1 << (n - 1)) + solve(g, h - 1, k - 1, n - 1, 0);
}
min = std::min({a1, a2, a3, a4});
return dp[g][h][k][n][c] = min;
} else {
int min, a1, a2, a3, a4;
min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
if (g - 2 + h >= k && k <= n - 1) {
a1 = solve(g - 1, h - 1, k, n - 1, 0);
}
if (g - 2 + h >= k - 1 && k - 1 <= n - 1) {
a2 = (1 << (n - 1)) + solve(g - 1, h - 1, k - 1, n - 1, 1);
}
if (g - 1 + h >= k && k <= n - 1) {
a3 = solve(g - 1, h, k, n - 1, 1);
}
if (g - 1 + h >= k && k <= n - 1) {
a4 = solve(g, h - 1, k, n - 1, 1);
}
min = std::min({a1, a2, a3, a4});
return dp[g][h][k][n][c] = min;
}
}