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)