我可以说这是动态编程吗？

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

维基百科动态编程:

在数学,计算机科学,经济学和生物信息学中,动态规划是一种通过将其分解为更简单的子问题的集合来解决复杂问题的方法.

然而,这主要似乎面向优化问题,并且确定N是否是2的幂通常不被构造为优化问题.

从"计算机编程中的动态编程"部分:

有两个关键属性的问题,必须拥有动态编程适用:最优子和重叠的子问题(重点煤矿).如果通过将最优解与非重叠子问题相结合可以解决问题,则该策略称为"分而治之".这就是mergesort和quicksort未被归类为动态编程问题的原因.

最优子结构意味着可以通过将最优解与其子问题组合来获得给定优化问题的解.因此,设计动态编程解决方案的第一步是检查问题是否表现出这种最佳子结构.这种最佳子结构通常通过递归来描述.例如,给定图G =(V,E),从顶点u到顶点v的最短路径p表现出最佳子结构:在该最短路径p上取任何中间顶点w.如果p确实是最短的路径,那么它可以被分成从u到w的子路径p1和从w到v的p2,这样它们反过来确实是相应顶点之间的最短路径......

重叠子问题意味着子问题的空间必须很小,也就是说,任何解决问题的递归算法都应该反复解决相同的子问题,而不是生成新的子问题.例如,考虑用于生成斐波纳契数列的递归公式:Fi = Fi-1 + Fi-2,其中基本情况F1 = F2 = 1.然后F43 = F42 + F41,并且F42 = F41 + F40.现在F41正在F43和F42的递归子树中得到解决.尽管子问题的总数实际上很小(只有43个),但如果我们采用像这样的天真递归解决方案,我们最终会一遍又一遍地解决相同的问题.动态编程考虑到了这一事实,并且只解决了一次子问题.

虽然"N/2是2的幂？" 是一个相关的子问题是"N是2的幂？" 我们可以编写一个只解决一次子问题的例程,我们没有Fibonacci序列中存在的那种重叠.如果我们这样做,递归就不会很好.在这里,确实如此.向递归添加memoization是一种自上而下的DP技术,但如果从递归中可以接受O(log2 N)时间,则实际上这是不必要的.

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

以下是一些测试方法.

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

另一种方法是在n == 2时返回True,如果是非整数或奇数mod 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)这个表达式的作用是什么？; 还可以检查log(N)/ log(2)以查看它是否接近整数值,计算2到该幂,并测试相等性.最后两种方法都不是动态编程,但在实践中可能更适合这种简单的任务.