动态规划 - 原始计算器Python

Question

此分配旨在对原始计算器实现动态编程方法，该方法只能加1，乘以2并乘以3.因此，输入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) 

Answer 1

注意，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])