Eratosthenes的筛子是动态规划的一个例子吗？

Question

我对Eratosthenes的Sieve（用所有数字的数组和标记复合数的循环实现）是否是动态编程的一个例子感到有点困惑？有几个朋友告诉我它的实现方式是Bottom Up DP的一个例子，但是我很难看到它。究竟是什么子问题以及如何使用自上而下/递归实现SoE？多谢你们。

Answer 1

当然，我们可以将Eratosthenes筛选视为动态规划的一个例子。子问题将是所有复合数。跳过标记的数字是子问题重叠的完美演示，因为如果它们没有重叠，我们就不会跳过它们:)

我们可以递归地制定筛子的一种方法是：让f(N)代表Nth prime及其相关的筛状态。然后：

f(1) = (2, [4,6...])
f(N) = (q, join( Sieve, [q+q,q+q+q...]))
  '''a pair, of the next number q above p 
  _not_ in Sieve, and the Sieve with 
  all the multiples of this number q
  added into it (we'll place an upper
  bound on this process, practically)'''
    where (p, Sieve) = f(N - 1)
          q = next_not_in(p, Sieve)

我们来测试一下：

f(3) = 
    call f(2) =
        call f(1) =
        <-- return (2, [4,6...])
    <-- return (3, [4,6,8,9...])
<-- return (5, [4,6,8,9,10...])