DP：查找计算器的最短时间和打印操作

Question

我的任务不同于其他专门针对“原始计算器”问题的问题。 您将获得一个基本计算器，它可以对当前数字x执行以下三个操作：将x乘以2（对于时间b）、将x乘以3（对于时间c）或将1与x相加（对于时间a）。您的目标是给定一个正整数n，查找从0开始获取数字n所需的最短时间，并以这种格式打印获取数字所需的操作： x+1“添加” x*2“双” x*3“三重”

Sample Input:

25 1 4 5

Sample Output:

14
add
add
add
add
triple
double
add

第一步应该是显而易见的（我们在开始时有0，第一个操作在任何情况下都是“添加”（bc 0*2=0和0*3=0）：

input_data = [int(x) for x in input().split()]
n = input_data[0]
a = input_data[1]
b = input_data[2]
c = input_data[3]
def primitive_calc(n):
    oper = []
    time = []
    oper[0] = "add"
    time[0] = a

但是在那之后…我不知道如何设置x+1，x2，x3。节省时间应该不是问题（在列表中添加a，b，c并作为结果求和）。但是如何保存操作呢？ 请不要写确切的答案，而是给我一些想法和提示。任何帮助都将不胜感激

Answer 1

一个简单的迭代实现可以提供一个O（n）复杂度的解决方案

让我们称T[i]为到达i级的最短时间。那么

T[i+1] <= T[i] + a
T[2*i] <= T[i] + b
T[3*i] <= T[i] + c

关于获得最短时间所需遵循的路径，在每个步骤中，只要记住导致T[i]的选项S[i]就足够了

然后，一种可能的迭代实现是：

初始化

T[i] = infinite
T[1] = a
S[i] = Null
S[1] = add

迭代

Do i = 2 to n-1
    T[i+1] = min(T[i+1], T[i] + a) -> if min obtained, S[i+1] = add
    T[2*i] = min(T[i+1], T[i] + b) -> if min obtained, S[2*i] = double
    T[3*i] = min(T[i+1], T[i] + c) -> if min obtained, S[3*i] = triple
    

输出

Min cost = T[n]
Path: use the S[i] from S[n] in reverse order