正向动态规划最短路径

Question

我想问一下如何使它成为X到Y的最短路径。例如，X = 10和Y = 22，它需要2次操作，即+1和* 2该（X + 1）* 2 = Y

def main(): 
operations = ["+1","*2"] 
X,Y = eval(input("Please enter two positive integers for X and Y, where X < Y, separated by a comma: ")) 
def XtoY(operations,X,Y): 
    table = [None for x in range(Y+1)] 
    for a in range(X+1): 
     table[a] = [ ] 
    for i in range(X+1,Y-X+1): 
     for operation in operations: 
      if X >= Y: 
       continue 
      if operation == "+1": 
       b = i-1 
       if table[b] != None: 
        table[i] = table[b][:] 
        table[i].append(operation) 

      if operation == "*2": 
       c = (i-1)*2 
       if c > Y: 
        continue 
       if table[b] != None: 
        table[c] = table[b][:] 
        table[c].append(operation) 


    if table[-1] != None: 
            print('The minimum number of operations to make '+str(X)+' equal to '+str(Y)+' is ' ,len(table[-1])) 
            print('The sequence of operations is:') 
            print('Y = ',table[-1]) 
    else: 
            print('No solution possible') 
XtoY(operations,X,Y) 

主（）

然而，当我输入10和1000，它给：Please enter two positive integers for X and Y, where X < Y, separated by a comma: 10,1000 The minimum number of operations to make 10 equal to 1000 is 491 The sequence of operations is: Y = ['+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '+1', '*2']

Answer 1

X,Y = 10,1000 
operations = ["+1","*2"] 
def XtoY(operations,X,Y): 
    steps_num = [] 
    steps = [] 
    steps_num.append(0) 
    steps.append([]) 
    for i in range(X+1, Y+1): 
     if i/2 < X: 
      steps_num.append(steps_num[-1] + 1) 
      steps.append(list(steps[-1]) + ["+1"]) 
     elif i % 2 == 0 and steps_num[i/2 - X] < steps_num[i - 1 - X]: 
      steps_num.append(steps_num[i/2 - X] + 1) 
      steps.append(list(steps[i/2 - X]) + ["*2"]) 
     else: 
      steps_num.append(steps_num[-1] + 1) 
      steps.append(steps[-1] + ["+1"]) 
    return steps[-1] 

print XtoY(operations, X, Y) 

使用steps_num记录至少步骤编号达到值i从价值X，使用steps记录如何从价值X 达到i我们知道：和Y

• steps_num[0] = 0 #from X to X
• steps[0] = [] #from X to X

为每个值i之间X

• steps_num[i - X] = steps_num[i - 1 - X] if i is odd
• steps_num[i - X] = steps_num[i - 1 - X] if i/2 < X
• steps_num[i - X] = steps_num[i - 1 - X] if steps_num[i - 1 - X] < steps_num[i/2 - X]
• steps_num[i - X]= steps_num[i/2 - X] if steps_num[i - 1 -X] > steps_num[i/2 - X]