python - 动态规划 - 原始计算器 Python

<分区>

此作业旨在对只能加 1、乘以 2 和乘以 3 的原始计算器实现动态编程方法。因此，输入 n 确定达到 n 的最小运算次数。我实现了一个非常幼稚的 dp 或者我认为是 dp 方法。它不工作。我没有其他人要问。对于 n = 5 的输入，下面的输出是:([0, 1, 2, 2, 3, 4], [1, 1, 2, 3, 4, 5]) 而有两个正确的输出列表编号 = [1, 2, 4, 5] 或 [1, 3, 4, 5]。一些帮助将不胜感激。

def DPmin_operations(n):

numbers = []
minNumOperations = [0]*(n+1)
numOps = 0
numbers.append(1)

for k in range(1,n+1):
    minNumOperations[k] = 10000

    # for *3 operator
    if k % 3 == 0:
        numOps = minNumOperations[k//3] + 1
        if numOps < minNumOperations[k]:
            minNumOperations[k] = numOps
            numbers.append(k)
    # for *2 operator
    elif k % 2 == 0:
        numOps = minNumOperations[k//2] + 1
        if numOps < minNumOperations[k]:
            minNumOperations[k] = numOps
            numbers.append(k)
    # for + 1 operator 
    elif k >= 1:
        numOps = minNumOperations[k - 1] + 1
        if numOps < minNumOperations[k]:
            minNumOperations[k] = numOps
            numbers.append(k)

return (minNumOperations, numbers)

最佳答案

请注意，elif block 实际上应该是 if block 。目前，您使用的是贪心算法，总是试图除以 3；如果失败，则尝试除以 2；如果失败，则减去 1。一个数字可能被 6 整除，因此所有三个选项都是可能的，但除以 2 比除以 3 更优化。

至于获取数字列表，请在最后执行。存储所有可能的 parent ，然后从您的目标向后工作，看看您是如何到达那里的。

def dp_min_ops(n):
    all_parents = [None] * (n + 1)
    all_min_ops = [0] + [None] * n

    for k in range(1, n + 1):
        curr_parent = k - 1
        curr_min_ops = all_min_ops[curr_parent] + 1

        if k % 3 == 0:
            parent = k // 3
            num_ops = all_min_ops[parent] + 1
            if num_ops < curr_min_ops:
                curr_parent, curr_min_ops = parent, num_ops

        if k % 2 == 0:
            parent = k // 2
            num_ops = all_min_ops[parent] + 1
            if num_ops < curr_min_ops:
                curr_parent, curr_min_ops = parent, num_ops

        all_parents[k], all_min_ops[k] = curr_parent, curr_min_ops

    numbers = []
    k = n
    while k > 0:
        numbers.append(k)
        k = all_parents[k]
    numbers.reverse()

    return all_min_ops, numbers

print(dp_min_ops(5))   # ([0, 1, 2, 2, 3, 4], [1, 3, 4, 5])
print(dp_min_ops(10))  # ([0, 1, 2, 2, 3, 4, 3, 4, 4, 3, 4], [1, 3, 9, 10])

关于python - 动态规划 - 原始计算器 Python，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37561224/

上一篇：python - 将行连接到python中的字符串

下一篇：python - 系列的第一个元素在 numpy 中跨越阈值，处理永不跨越的系列

相关文章：

python - 如何在 matplotlib 图上的鼠标单击之间绘制线条？

arrays - 数字的计数集在整数数组中具有相同的差异

arrays - 非连续元素的最大总和(来自任意位置的 k 个元素)

algorithm - 匹配大小的动态规划(最小差异)

python - Pytest 捕获某个测试的标准输出

python - 如何使用 Keras TimeseriesGenerator

python - numpy 数组 : sequence too large

python - opencv-python imshow 在 mac 中给出错误

algorithm - 找到连续的子序列，使得数字总和的立方体最多为 y

recursion - 使用 HashMap 而不是表进行内存