我能说这是动态规划吗？
Can I say that this is dynamic programming?
我是动态规划的新手，根据我的理解，动态规划是您使用计算结果来检查您的函数是否正确的地方。我在一次采访中被要求实现一种方法来检查 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
维基百科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 的幂通常不被视为优化问题。
来自第 "dynamic programming in computer programming" 部分：
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.
虽然 "is N / 2 a power of 2?" 是 "N a power of 2?" 的一个相关子问题，并且我们可以编写一个例程来仅解决此类子问题一次，但我们没有斐波那契中存在的那种重叠顺序。如果我们这样做，递归将不会很好地工作。在这里，确实如此。在递归中添加记忆是一种自上而下的 DP 技术，但如果递归可以接受 O(log2 N) 时间，那么这里实际上是不必要的。
看起来你构建了一个 2 的幂列表，而不是将问题分解成更小的部分，（虽然你没有缓存列表，但每次都构建它，但是缓存或不缓存并不意味着它是或不是动态规划）并测试输入是否在列表中，如果不在列表中，是否可以通过扩展列表找到它。虽然我认为您的测试还可以，但与动态规划的联系更加脆弱。
这里有一些其他的测试方法。
测试一个数是否为 2 的幂的一种方法是以 2 为底数表示它，并确保只有一位设置为 1，其余为零。许多语言都有办法获得整数的替代基本表示形式。 2 的幂也有独特的八进制和十六进制字符串表示形式。
另一种方法是 return n==2 为真，return 为非整数或奇数 mod 2 为假，否则测试 n/2 是否为 a 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 的该次幂，并测试是否相等。最后两种方法都不是动态规划，但在实践中可能更适合这种简单的任务。
这是一种不同于回避和记忆的方法——自下而上 table。您从可能的最小值开始计算结果，然后构建更大的值。听起来像递归，但行为不同。这是另一个起点。另见 Can recursion be dynamic programming?
def is_power_of_two(n):
results = {}
for i in range(1, n + 1):
if i == 2:
results[i] = True
elif i % 2 != 0:
results[i] = False
else:
results[i] = results[i/2]
return results[n]
优点：
- 与递归相比，避免了栈帧问题
- 允许优化巨大数据集的存储值
（当您使用非常大的数字和有限的内存调用函数时，您可以通过删除所有条目
> i/2 来清理 results）
我是动态规划的新手，根据我的理解，动态规划是您使用计算结果来检查您的函数是否正确的地方。我在一次采访中被要求实现一种方法来检查 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
维基百科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 的幂通常不被视为优化问题。
来自第 "dynamic programming in computer programming" 部分：
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.
虽然 "is N / 2 a power of 2?" 是 "N a power of 2?" 的一个相关子问题，并且我们可以编写一个例程来仅解决此类子问题一次，但我们没有斐波那契中存在的那种重叠顺序。如果我们这样做，递归将不会很好地工作。在这里，确实如此。在递归中添加记忆是一种自上而下的 DP 技术，但如果递归可以接受 O(log2 N) 时间，那么这里实际上是不必要的。
看起来你构建了一个 2 的幂列表，而不是将问题分解成更小的部分，（虽然你没有缓存列表，但每次都构建它，但是缓存或不缓存并不意味着它是或不是动态规划）并测试输入是否在列表中，如果不在列表中，是否可以通过扩展列表找到它。虽然我认为您的测试还可以，但与动态规划的联系更加脆弱。
这里有一些其他的测试方法。
测试一个数是否为 2 的幂的一种方法是以 2 为底数表示它，并确保只有一位设置为 1，其余为零。许多语言都有办法获得整数的替代基本表示形式。 2 的幂也有独特的八进制和十六进制字符串表示形式。
另一种方法是 return n==2 为真，return 为非整数或奇数 mod 2 为假，否则测试 n/2 是否为 a 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 的该次幂，并测试是否相等。最后两种方法都不是动态规划，但在实践中可能更适合这种简单的任务。
这是一种不同于回避和记忆的方法——自下而上 table。您从可能的最小值开始计算结果，然后构建更大的值。听起来像递归，但行为不同。这是另一个起点。另见 Can recursion be dynamic programming?
def is_power_of_two(n):
results = {}
for i in range(1, n + 1):
if i == 2:
results[i] = True
elif i % 2 != 0:
results[i] = False
else:
results[i] = results[i/2]
return results[n]
优点：
- 与递归相比，避免了栈帧问题
- 允许优化巨大数据集的存储值
（当您使用非常大的数字和有限的内存调用函数时，您可以通过删除所有条目
> i/2来清理results）