3

给定一个正整数 A。目标是使用以下规则构建以 A 结尾的最短整数序列：

  1. 序列的第一个元素是 1
  2. 每个连续元素都是任何两个前面元素的总和（也允许将单个元素添加到自身）
  3. 每个元素都大于前面的所有元素；也就是说，序列是递增的。

例如，对于 A = 42，可能的解决方案是：

[1, 2, 3, 6, 12, 24, 30, 42]

A = 42 的另一种可能的解决方案是：

[1, 2, 4, 5, 8, 16, 21, 42]

读完问题陈述后，我首先想到的是动态规划（DP），因此我将其表达为搜索问题并尝试编写递归解决方案。

直到 A = 8 的搜索空间是：

                1
                |
                2
               / \
              /   \            
             3     4
            /|\   /|\
           / | \ 5 6 8
          /  |  \
         4   5   6
       /| |\  
      5 6 7 8

我们可以看到 4 出现在两个地方，但在这两种情况下 4 的孩子都是不同的。在一种情况下，先验序列是 [1, 2, 4]。在另一种情况下，先验序列是 [1, 2, 3, 4]。因此，我们不能说我们有重叠的子问题。有没有办法将DP应用于上述问题？或者我判断可以使用DP解决它是错误的？

4

3 回答 3

3

这是一个加法链...

http://en.wikipedia.org/wiki/Addition_chain

没有已知的算法可以计算给定数字的最小加法链，并保证合理的时序或小内存使用。然而，存在几种计算相对较短链的技术。一种非常著名的计算相对较短的加法链的技术是二元法，类似于平方取幂。其他著名的方法是因子方法和窗口方法。

另请参阅：在电子、通信和计算机科学基础的 IEICE 交易中生成短加法链的新方法。

于 2012-05-04T07:08:01.543 回答
2

这个问题有一个纯动态规划的解决方案。但与所有 DP 解决方案一样，内存和时间的复杂度都是 N 平方。所以它可能是一个太空猪。但这里是专为 DP 爱好者设计的 DP 解决方案的症结所在：

概括：

而不是找到N即加法链的最小长度。l(N)，我们要找到包含 i 和 j 的加法链的最小长度，其中 i ≤ j 和 j 是链中的最大值。将此长度称为 A(i, j)。显然，我们有

  1. l(N) = A(1, N) = A(N,N)
  2. A(1, N) = A(2, N) 如果 N ≥ 2
  3. A(1, N) = 1+min (A(i, j) 对于 1 ≤ i ≤ j < N 并且 i+j=N

预先计算

为了通过使用较小的 A(i, j) 来计算任何 A(m, n)，这是一个典型的 DP 步骤，我们应用了许多启发式方法。

H1：沿途为 (3) 的最小部分保持 S(i+j)。然后

 A(1, n) = A(2, n) = A(n, n) = S(n)+1

对于其他m，我们通过在链中最多引入一个新元素来减少n，并且有了这样一个新元素，我们只需要多一步来得出A（m，n）。可能性是

H2：如果 n 是偶数，我们尝试将 n/2 引入链
H3：尝试将 nm 引入链
H4：尝试将 n-1 引入链
H5：尝试将 n-2 引入链（当n>2)

所以 A(m, n) 取 m 的 A 的最小值和基于 H2-H5 的减少的 n，加 1。

例如，通过分别应用 H2-H5，A(52, 100) = 1+min(A(50, 52), A(48, 52), A(52, 99), A(52, 98))。

于 2017-08-21T09:15:29.443 回答
-1

由于规则#2，

每个连续元素是任何两个前面元素的总和

该算法确实依赖于重复的子问题，因此动态规划将适合解决它。

于 2012-05-04T07:27:41.907 回答