python - 动态编程-原始计算器Python

This question already has an answer here:

Dynamic programming for primitive calculator
                                
                                    （1个答案）
                                
                        
                                3年前关闭。
            
                    
此分配旨在为原始计算器实现动态编程方法，该方法只能加1，乘以2和乘以3。因此，在输入n的情况下，确定达到n的最小操作数。我已经实现了非常幼稚的dp或我认为是dp的方法。它不起作用。我没有人要问。对于n = 5的输入，以下输出为：（[0，1，2，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块实际上应该是if块。目前，您使用的贪婪算法总是尝试除以3；如果失败，则尝试除以2；如果失败，则减1。数字可能被6整除，因此所有三个选项都是可能的，但除以2则比除以3更好。

至于获取数字列表，请在最后完成。存放所有可能的父母，然后从您的目标开始倒退，看看您是如何到达那里的。

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/