我正在尝试解决以下问题：
找到具有k个1位且是两个n位整数之和的最小n位整数c，这些整数具有g、h位设置为1。 g、h、k <= n。
这里的n位整数意味着我们可以使用所有n位，即这样一个整数的最大值为2 ^ n-1。所描述的整数可能根本不存在。显然，情况k> g + h没有解决方案，对于g + h = k，答案只是2 ^ k-1（前面有k-n个0）。
至于程序应该执行的一些示例：
同样地，
这个想法并不难，但我对这些东西并不是很有经验，即使对于最简单的情况，我的算法也无法工作。我选择了自上而下的方法，但很难考虑到所有的边角情况。我不确定是否正确选择了递归基础等。我的算法甚至不能处理最基本的情况
找到具有k个1位且是两个n位整数之和的最小n位整数c，这些整数具有g、h位设置为1。 g、h、k <= n。
这里的n位整数意味着我们可以使用所有n位，即这样一个整数的最大值为2 ^ n-1。所描述的整数可能根本不存在。显然，情况k> g + h没有解决方案，对于g + h = k，答案只是2 ^ k-1（前面有k-n个0）。
至于程序应该执行的一些示例：
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;
}
}
2^(n + 1) - 1" - 实际上应该是2^n - 1。 - Gassa