给定整数n和一组操作，将n减少至1个步骤

Question

在给定整数n上我们可以使用以下操作：

1. 如果n可以除以3：除以3。
2. 如果n可以除以2：除以2。
3. 减去1。

如何找到最少的步骤达到1的策略？

Answer 1

正如Mbeckish所述，您可以将其视为BFS遍历，其时间和空间复杂性比自下而上的DP方法要好得多。您还可以在遍历中应用分支并绑定（B＆amp; b）启发式启发式词，以便您在我们之前已经看到过标记的值的节点上修剪树的分支。与实际的b＆amp; bemp; hamp;这不会修剪最佳解决方案，因为它不涉及对最佳解决方案可能在哪里的任何有根据的猜测。我将举一个视觉示例，并使算法降低到0以更好地说明。

这是一棵完整的操作树，减少了10至0：

   --------10---------
   5         -----9----
---4---     -3-      ------8------  
2    -3-    1 2    --4--         7        
1    1 2    0 1    2  -3-   -----6------   
0    0 1      0    1  1 2   2   -3-    5   
       0           0  0 1   1   1 2  --4-- 
                        0   0   0 1  2  -3-
                                  0  1  1 2
                                     0  0 1
                                          0 

由于我们正在做BFS，因此我们实际上会在第一个零停止，如下所示，而不是建立树的更深部分：

   --------10------
   5         -----9--------
---4---     -3-     ------8------  
2    -3-    1 2     4           7        
1    1 2    0 

但是，我们可以通过b'amp; b heuristis的进一步减少分支的数量（，这对大量数字都产生了巨大的影响）：

   --------10------
   5         -----9--------
   4         3            8
   2         1            7
             0 

时间复杂度： O(log n) 空间复杂度： O(log n) ^{（我认为）}

下面是Python 3代码，输入1 GOOGOL（10^100），在我的计算机上运行约8秒，大约350 MB的RAM。您也可以在https://repl.it/b3oq/76

上在线运行。

from collections import deque
def number_of_steps(i):
    Q = deque()
    seen_before = set()
    steps = 0
    Q.append((i, steps))
    while True:
        j, steps = Q.popleft()
        if j == 1:
            return steps
        if j % 3 == 0:
            branch(Q, seen_before, steps, j // 3)
        if j % 2 == 0:
            branch(Q, seen_before, steps, j // 2)
        branch(Q, seen_before, steps,  j - 1)
def branch(Q, seen_before, steps, k):
    if k not in seen_before:
        seen_before.add(k)
        Q.append((k, steps + 1))
import time
n = 10**100
print('input:', n)
start = time.time()
steps = number_of_steps(n)
end = time.time()
print('runtime (seconds):', end - start)
print('number of steps:', steps)

Answer 2

有快速的动态编程解决方案： -

minSteps(N) = Minimum(minSteps(N/3),minSteps(N/2),minSteps(N-1)) + 1

注意：如果n不容易由3或2除外，则不要将其包括在DP方程中。

时间复杂性： O(N)空间复杂性： O(N)

DP解决方案的Java代码： -

public static int decompose(int n) {
        int steps [] = new int[n+1];
        steps[1] = 0;
        for(int i=2;i<=n;i++) {
            int min = n;
            if(i%2==0) {
                min = Math.min(min,steps[i/2]);
            }
            if(i%3==0) {
                min = Math.min(min,steps[i/3]);
            }
            min = Math.min(min,steps[i-1]);
            steps[i] = min + 1;
        }
        int k =n;
        System.out.println("Steps:");
        while(k>1) {
            if(k%3==0&&steps[k/3]+1==steps[k]) {
                System.out.println("div 3");
                k=k/3;
            }
            else if(n%2==0&&steps[k/2]+1==steps[k]) {
                System.out.println("div 2");
                k=k/2;
            }
            else {
                System.out.println("minus 1");
                k=k-1;
            }
        }
        return(steps[n]);
    }

Answer 3

将其视为宽至的树遍历。

根节点是N。操作是导致其子女的边缘，

到达1。

时停止

从根到1的路径是解决方案。