python - 我能说这是动态规划吗？

Question

我是动态规划的新手，根据我的理解，动态规划是使用计算结果来检查函数是否正确的地方。我在一次采访中被要求实现一种方法来检查 n 是否为 2 的幂。所以，我想到了这个。

def isPowerOfTwo(self, n):
    power_of_two = [1]
    is_power_of_two = False
    if n == 0:
        return False

    if n == 1:
        return True

    while True:
        power_of_two.append(power_of_two[-1] * 2)
        if n == power_of_two[-1]:
            is_power_of_two = True
            break

        if power_of_two[-1] > n:
            break

    return is_power_of_two

Answer 1

维基百科 dynamic programming :

In mathematics, computer science, economics, and bioinformatics, dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

但是，这似乎主要面向优化问题，确定 N 是否为 2 的幂通常不被视为优化问题。

摘自“计算机编程中的动态规划”部分:

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping subproblems (emphasis mine). If a problem can be solved by combining optimal solutions to non-overlapping subproblems, the strategy is called "divide and conquer" instead. This is why mergesort and quicksort are not classified as dynamic programming problems.

Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its subproblems. Consequently, the first step towards devising a dynamic programming solution is to check whether the problem exhibits such optimal substructure. Such optimal substructures are usually described by means of recursion. For example, given a graph G=(V,E), the shortest path p from a vertex u to a vertex v exhibits optimal substructure: take any intermediate vertex w on this shortest path p. If p is truly the shortest path, then it can be split into subpaths p1 from u to w and p2 from w to v such that these, in turn, are indeed the shortest paths between the corresponding vertices...

Overlapping subproblems means that the space of subproblems must be small, that is, any recursive algorithm solving the problem should solve the same subproblems over and over, rather than generating new subproblems. For example, consider the recursive formulation for generating the Fibonacci series: Fi = Fi−1 + Fi−2, with base case F1 = F2 = 1. Then F43 = F42 + F41, and F42 = F41 + F40. Now F41 is being solved in the recursive subtrees of both F43 as well as F42. Even though the total number of subproblems is actually small (only 43 of them), we end up solving the same problems over and over if we adopt a naive recursive solution such as this. Dynamic programming takes account of this fact and solves each subproblem only once.

尽管“N/2 是 2 的幂吗？”是与“N 是 2 的幂”相关的子问题吗？我们可以编写一个例程来只解决这些子问题一次，我们没有斐波那契数列中存在的那种重叠。如果我们这样做，递归将不会很好地工作。在这里，确实如此。在递归中添加内存是一种自上而下的 DP 技术，但如果递归可以接受 O(log2 N) 时间，那么这里实际上是不必要的。

看起来你没有将问题分解成更小的部分，而是构建了一个 2 的幂列表，(虽然你没有缓存列表，但每次都构建它，但是缓存或不缓存并不意味着它是或者不是动态规划)并测试输入是否在列表中，如果不在列表中，是否可以通过扩展列表找到它。虽然我认为您的测试还可以，但与动态规划的联系更加脆弱。

这里有一些其他的测试方法。

测试一个数是否为 2 的幂的一种方法是以 2 为底数表示它，并确保只有一位设置为 1，其余为零。许多语言都有办法获得整数的替代基本表示形式。 2 的幂也有独特的八进制和十六进制字符串表示形式。

另一种方法是对 n==2 返回 True，如果非整数或奇模 2 则返回 False，否则用递归测试 n/2 是否是 2 的幂。很多数学动态规划都是递归的。

def isPowerOf2(n):
        if n%2==1:
            return False
        if n==2:
            return True
        else:
            return isPowerOf2(n/2)

我们可以像这样对其进行类型检查和内存:

powers_of_2 = [2]
def isPowerOf2(n):
    if type(n)!=type(1):
        raise TypeError("isPowerOf2(): integer value required")
    if n%2==1:
        return False
    if n in powers_of_2:
        return True
    if n<powers_of_2[-1]:
        return False
    else:
        result =  isPowerOf2(n/2)
        if result:
            powers_of_2.append(n)
        return result

并用下面的例子进行测试:

>>> import power2 # name of our python code script file
>>> power2.isPowerOf2(256)
True
>>> power2.powers_of_2
[2, 4, 8, 16, 32, 64, 128, 256]

对于更短的内容，按照@Tris Nefzger 的建议，请参阅:n & (n-1) what does this expression do? ;还可以检查 log(N)/log(2) 以查看它是否接近整数值，计算 2 的该次幂，并测试是否相等。最后两种方法都不是动态规划，但在实践中可能更适合这种简单的任务。