这项作业的目的是实现一个动态规划的方法,一个原始计算器只能加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
块实际上应该是if
块。目前,您使用的贪婪算法总是试图除以3;如果这失败,那么尝试除以2;如果失败,则减去1。一个数可以被6整除,所以这三个选项都是可能的,但是除以2比除以3更好。在至于得到你的号码清单,在最后再做。存储所有可能的父母,然后从你的目标向后看,看看你是怎么做到的。在
相关问题 更多 >
编程相关推荐