python - 原始计算器 - 动态方法

Question

我在获得以下问题的正确解决方案时遇到了一些麻烦:

Your goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.

更具体地说，我在下面的评论中有测试用例。

 # Failed case #3/16: (Wrong answer)
    # got: 15 expected: 14
    # Input:
    # 96234
    #
    # Your output:
    # 15
    # 1 2 4 5 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
    # Correct output:
    # 14
    # 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
    #  (Time used: 0.10/5.50, memory used: 8601600/134217728.)


    def optimal_sequence(n):
        sequence = []

        while n >= 1:
            sequence.append(n)

            if n % 3 == 0:
                n = n // 3
                optimal_sequence(n)

            elif n % 2 == 0:
               n = n // 2
               optimal_sequence(n)

            else:
               n = n - 1
               optimal_sequence(n)

        return reversed(sequence)

    input = sys.stdin.read()
    n = int(input)
    sequence = list(optimal_sequence(n))
    print(len(sequence) - 1)
    for x in sequence:
        print(x, end=' ')

看起来我应该在输出 4 和 5 的地方输出 9，但我不确定为什么不是这样。解决此问题的最佳方法是什么？

Answer 1

你正在做一个贪婪的方法。 当 n == 10 时，您检查它是否可以被 2 整除，假设这是最佳步骤，但在这种情况下这是错误的。

您需要做的是适当的动态规划。 v[x] 将保留获得结果 x 的最少步数。

def solve(n):
  v = [0]*(n+1)  # so that v[n] is there
  v[1] = 1  # length of the sequence to 1 is 1
  for i in range(1,n):
    if not v[i]: continue
    if v[i+1] == 0 or v[i+1] > v[i] + 1: v[i+1] = v[i] + 1
    # Similar for i*2 and i*3
  
  solution = []
  while n > 1:
    solution.append(n)
    if v[n-1] == v[n] - 1: n = n-1
    if n%2 == 0 and v[n//2] == v[n] -1: n = n//2
    # Likewise for n//3
  solution.append(1)
  return reverse(solution)