原始计算器 - 动态方法

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)

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] = Math.min(1 + arr[i / 2], arr[i]);
        if (i % 3 == 0) arr[i] = Math.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;
}

Answer 3

List<Integer> sequence = new ArrayList<Integer>();
     
while (n>0) {
    sequence.add(n);
        if (n % 3 == 0&&n % 2 == 0)
            n=n/3;
        else if(n%3==0)
            n=n/3;
        else if (n % 2 == 0&& n!=10)
            n=n/2;
        else
            n=n-1;
    }
Collections.reverse(sequence);
return sequence;

Answer 4

这是我对问题的动态规划（自下而上和记忆）解决方案：

public class PrimitiveCalculator {

    1. public int minOperations(int n){
    2.    int[] M = new int[n+1];
    3.    M[1] = 0; M[2] = 1; M[3] = 1;
    4.    for(int i = 4; i <= n; i++){
    5.        M[i] = M[i-1] + 1;
    6.        M[i] = Math.min(M[i], (i %3 == 0 ? M[i/3] + 1 : (i%3 == 1 ? M[(i-1)/3] + 2 : M[(i-2)/3] + 3)));
    7.        M[i] = Math.min(M[i], i%2 == 0 ? M[i/2] + 1: M[(i-1)/2] + 2);
    8.    }
    9.    return M[n];
   10. }

    public static void main(String[] args) {
        System.out.println(new PrimitiveCalculator().minOperations(96234));
    }
}

在继续解释算法之前，我想添加一个快速免责声明：

A DP solution is not reached at first attempt unless you have good experience solving lot of DP problems.

通过DP求解的方法

如果您对 DP 问题不满意，那么解决问题的最佳方法如下：

尝试获得有效的强力递归解决方案。
一旦我们有了递归解决方案，我们就可以通过添加记忆来寻找减少递归步骤的方法，我们尝试记住已经在递归步骤中解决的较小规模子问题的解决方案 - 这通常是自上而下的解决方案。
记忆后，我们尝试翻转解决方案并自下而上解决（我上面的 Java 解决方案是自下而上的解决方案）
完成上述 3 个步骤后，您就获得了 DP 解决方案。

现在来解释上面的解决方案：

给定一个数字“n”并且仅给出 3 个操作 {+1, x2, x3}，给出从 1 到达“n”所需的最少操作数通过递归公式：

min_operations_to_reach(n) = Math.min(min_operations_to_reach(n-1), min_operations_to_reach(n/2), min_operations_to_reach(n/3))

如果我们翻转记忆过程并从数字 1 本身开始，那么上面的代码开始变得更有意义。从 1、2、3 的小案例开始 min_operations_to_reach(1) = 0 因为我们不需要做任何操作。 min_operations_to_reach(2) = 1 因为我们可以做 (1 +1) 或 (1 x2)，在这两种情况下操作数都是 1。类似地，min_operations_to_reach(3) = 1 因为我们可以将 1 乘以 3，这是一次运算。

现在取任意数 x > 3，min_operations_to_reach(x) 是以下 3 中的最小值：

min_operations_to_reach(x-1) + 1 因为无论达到 (x-1) 的最小操作数是多少，我们都可以将其加 1 以获得操作数使其成为数字 x.
或者，如果我们考虑用 1 乘以 3 得到数字 x，那么我们必须考虑以下 3 个选项：
- 如果 x 能被 3 整除则 min_operations_to_reach(x/3) + 1,
- 如果 x 不能被 3 整除那么 x%3 可以是 1，在这种情况下它的 min_operations_to_reach((x-1)/3) + 2, +2 因为乘法需要一个运算乘以 3 并且需要另一个操作来加 1 以使数字 'x'
- 同理如果x%3 == 2，那么这个值就是min_operations_to_reach((x-2)/3) + 3。+3是因为1乘以3然后加两个1随后使数字 x.
或者，如果我们考虑使用乘以 2 从 1 得到数字 x，那么我们必须考虑以下 2 个选项：
- 如果 x 可以被 2 整除那么它的 min_operations_to_reach(x/2) + 1
- 如果 x%2 == 1 那么它的 min_operations_to_reach((x-1)/2) + 2.

取以上3中的最小值，可以得到达到x的最少操作次数。这就是上面代码中第 5、6 和 7 行所做的。

Answer 5

def DPoptimal_sequence(n,operations):
    MinNumOperations=[0]
    l_no=[]
    l_no2=[]

    for i in range(1,n+1):
        MinNumOperations.append(None)
        for operation in operations:
            if operation==1:
                NumOperations=MinNumOperations[i-1]+1

            if operation==2 and i%2==0:
                NumOperations=MinNumOperations[int(i/2)]+1
            if  operation==3 and i%3==0:
                NumOperations=MinNumOperations[int(i/3)]+1
            if MinNumOperations[i]==None:
                MinNumOperations[i]=NumOperations
            elif NumOperations<MinNumOperations[i]:
                MinNumOperations[i]=NumOperations
        if MinNumOperations[i] ==  MinNumOperations[i-1]+1:
            l_no2.append((i,i-1))
        elif MinNumOperations[i] ==  MinNumOperations[int(i/2)]+1 and i%2 == 0:
            l_no2.append((i,int(i/2)))
        elif MinNumOperations[i] ==  MinNumOperations[int(i/3)]+1 and i%3 == 0:
            l_no2.append((i,int(i/3)))

        l_no.append((i,MinNumOperations[i]-1))
    #print(l_no)
    #print(l_no2)
    x=MinNumOperations[n]-1
    #print('x',x)
    l_no3=[n]
    while n>1:
        a,b = l_no2[n-1]
        #print(a,b)
        if b == a-1:
            n = n-1
            #print('1111111111111')
            #print('n',n)
            l_no3.append(n)
        elif b == int(a/2) and a%2==0:
            n = int(n/2)
            #print('22222222222222222')
            #print('n',n)
            l_no3.append(n)
        elif b == int(a/3) and a%3==0:
            n = int(n/3)
            #print('333333333333333')
            #print('n',n)
            l_no3.append(n)
    #print(l_no3)
    return x,l_no3

Answer 6

def optimal_sequence(n):
hop_count = [0] * (n + 1)

hop_count[1] = 1
for i in range(2, n + 1):
    indices = [i - 1]
    if i % 2 == 0:
        indices.append(i // 2)
    if i % 3 == 0:
        indices.append(i // 3)

    
    min_hops = min([hop_count[x] for x in indices])

    
    hop_count[i] = min_hops + 1


ptr = n
optimal_seq = [ptr]
while ptr != 1:

    
    candidates = [ptr - 1]
    if ptr % 2 == 0:
        candidates.append(ptr // 2)
    if ptr % 3 == 0:
        candidates.append(ptr // 3)

    
    ptr = min(
        [(c, hop_count[c]) for c in candidates],
        key=lambda x: x[1] 
    )[0]
    optimal_seq.append(ptr)

return reversed(optimal_seq)

Answer 7

private int count(int n, Map<Integer, Integer> lookup) {
        if(lookup.containsKey(n)) {
            return lookup.get(n);
        }
        
        if(n==1) {
            return 0;
        } else {
            int result;
            if(n%2==0 && n%3==0) {
                result =1+ 
                        //Math.min(count(n-1, lookup), 
                      Math.min(count(n/2, lookup), 
                            count(n/3, lookup));
            } else if(n%2==0) {
                result = 1+ Math.min(count(n-1, lookup), 
                                count(n/2, lookup));
            } else if(n%3==0) {
                result = 1+ Math.min(count(n-1, lookup), count(n/3, lookup));
            } else {
                result = 1+ count(n-1, lookup);
            }
            //System.out.println(result);
            lookup.put(n, result);
            return result;
        }
    }

原始计算器 - 动态方法

Primitive Calculator - Dynamic Approach

python

algorithm

recursion

dynamic-programming

memoization