最小步长到一

algorithm math java dynamic-programming

2022-09-04 04:29:17

问题陈述：

对于正整数，可以执行以下 3 个步骤中的任何一个。

从中减去 1。（ n = n - 1 ）
如果可被 2 整除，则除以 2。（如果 n % 2 == 0 ，则 n = n / 2 ）
如果可被 3 整除，则除以 3。（如果 n % 3 == 0 ，则 n = n / 3 ）。

现在的问题是，给定一个正整数n，找到需要n到1的最小步数

例如：

当 n = 1 时，输出：0
当 n = 4 时，输出： 2 （ 4 /2 = 2 /2 = 1 ）
对于 n = 7，输出： 3 （ 7 -1 = 6 /3 = 2 /2 = 1 ）

我知道使用动态编程和整数数组的解决方案。这是代码。

    public int bottomup(int n) {
            //here i am defining an integer array
            //Exception is thrown here, if the n values is high.
            public int[] bu = new int[n+1];
            bu[0] = 0;
            bu[1] = 0;
            for(int i=2;i<=n;i++) {
                    int r = 1+bu[i-1];
                    if(i%2 == 0) r = Math.min(r,1+bu[i/2]);
                    if(i%3 == 0) r = Math.min(r,1+bu[i/3]);
                    bu[i] = r;
            }
            return bu[n];
    }

但我想用更少的空间解决这个问题。如果 n=100000000，此解决方案会在 java 中抛出 OutofMemoryError。我不想增加堆空间。有没有人有使用更少空间的解决方案？

请注意，这个问题不能用贪婪的算法来解决。使用一个 while 循环并检查可整除的 3 和可被 2 整除是行不通的。您必须使用动态规划。请建议是否有任何解决方案使用更少的空间。

例如：

对于 n = 10 贪婪算法是 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1，这需要 4 个步骤。其中解应该是 10-1 = 9 / 3 = 3 / 3 = 1，3 步。

我甚至尝试了自上而下的解决方案。

    public int[] td = null;
    public int topdown(int n) {
            if(n <= 1) return 0;
            int r = 1+topdown(n-1);
            if(td[n] == 0) {
                    if(n%2 == 0) r = Math.min(r,1+topdown(n/2));
                    if(n%3 == 0) r = Math.min(r,1+topdown(n/3));
                    td[n] = r;
            }
            return td[n];
    }

它在 n=10000 时失败。

答案 1

一个想法是，在任何迭代中，您只需要的值 to 。因此，您可以继续丢弃数组。r/3r1/3rd

我不熟悉，但你可以使用一个：JavaC++double ended queue (deque)

你不断从后面添加德克。
当时，您不需要和。因此，您从队列的前面弹出两个元素。i = 6bu[0]bu[1]

deque 容器支持随机访问。[ ]

编辑：同样按照注释中的建议，您应该将数据类型更改为较小的数据类型，因为最大步骤数应为( (log N) to base 2)

编辑2：正如Dukeling所指出的，在Java中似乎没有现成的适合deque的实现，不会损害时间复杂性。你可以像C++那样以自己的方式实现它（我听说它是作为向量的向量实现的，内部向量的大小与元素总数相比很小）。

答案 2

递归解决方案针对此问题


public static int countMinStepsTo1(int n){

      if(n==1)
      {
          return 0;
      } 
      int count1,count2=Integer.MAX_VALUE,count3=Integer.MAX_VALUE;

      count1 = countMinStepsTo1(n-1);

       if((n%2)==0)
       {
           count2=countMinStepsTo1(n/2);
       }
        if((n%3)==0)
        {
            count3=countMinStepsTo1(n/3);
        }

        return 1+Math.min(count1,Math.min(count2,count3));
    }

DP Approch 对于此问题

public static int countstepsDP(int n)
    {
        int storage[] = new int[n+1];
        storage[1]=0;

        for(int i=2; i<=n;i++)
        {
            int min=storage[i-1];
            if(i%3==0)
            {
                if(min>storage[i/3])
                {
                    min=storage[i/3];
                }
            }
            if(i%2==0)
            {
                if(min>storage[i/2])
                {
                    min=storage[i/2];
                }
            }
            storage[i]=1+min;
        }

        return storage[n];

    }