我正在尝试解决以下问题：
找到最小的 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;
}
}