Find the smallest n-bit integer c that has k 1-bits and is the sum of two n-bit integers that have g,h bits set to 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,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,k,n - 1,0);
    }
    if (g + h >= k - 1 && k - 1 <= n - 1) {
      a2 = (1 << (n - 1)) + solve(g,k - 1,1);
    }
    if (g - 1 + h >= k - 1 && k - 1 <= n - 1) {
      a3 = (1 << (n - 1)) + solve(g - 1,0);
    }
    if (g + h - 1 >= k - 1 && k - 1 <= n - 1) {
      a4 = (1 << (n - 1)) + solve(g,h - 1,0);
    }
    min = std::min({a1,a4});
    return dp[g][h][k][n][c] = min;
  } else {
    int min,a4;
    min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
    if (g - 2 + h >= k && k <= n - 1) {
      a1 = solve(g - 1,0);
    }
    if (g - 2 + h >= k - 1 && k - 1 <= n - 1) {
      a2 = (1 << (n - 1)) + solve(g - 1,1);
    }
    if (g - 1 + h >= k && k <= n - 1) {
      a3 = solve(g - 1,1);
    }
    if (g - 1 + h >= k && k <= n - 1) {
      a4 = solve(g,1);
    }
    min = std::min({a1,a4});
    return dp[g][h][k][n][c] = min;
  }
}