原始计算器 - 动态方法

Question

我在解决以下问题时遇到了一些问题:

您的目标是正整数n,找到从数字1开始获取数字n所需的最小操作数.

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

 # 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=' ')

看起来我应该输出9输出4和5,但我不确定为什么不是这种情况.解决此问题的最佳方法是什么？

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+1):
    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)

Answer 2

还有一个解决方案

private static List<Integer> optimal_sequence(int n) {
    List<Integer> sequence = new ArrayList<>();

    int[] arr = new int[n + 1];

    for (int i = 1; i < arr.length; i++) {
        arr[i] = arr[i - 1] + 1;
        if (i % 2 == 0) arr[i] = min(1 + arr[i / 2], arr[i]);
        if (i % 3 == 0) arr[i] = min(1 + arr[i / 3], arr[i]);

    }

    for (int i = n; i > 1; ) {
        sequence.add(i);
        if (arr[i - 1] == arr[i] - 1)
            i = i - 1;
        else if (i % 2 == 0 && (arr[i / 2] == arr[i] - 1))
            i = i / 2;
        else if (i % 3 == 0 && (arr[i / 3] == arr[i] - 1))
            i = i / 3;
    }
    sequence.add(1);

    Collections.reverse(sequence);
    return sequence;
}