一步的最小步骤

Question

问题陈述 :

在正整数上,您可以执行以下3个步骤中的任何一个.

1. 从中减去1.(n = n - 1)
2. 如果它可被2整除,则除以2.(如果n%2 == 0,则n = n/2)
3. 如果它可被3整除,则除以3.(如果n%3 == 0,则n = n/3).

现在问题是,给定正整数n,找到将n取为1的最小步数

例如:

1. 对于n = 1,输出:0
2. 对于n = 4,输出:2(4/2 = 2/2 = 1)
3. 对于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,这个解决方案会抛出OutofMemoryError.我不想增加我的堆空间.是否有人使用更少的空间解决方案？

请注意这个问题不能用greedy algorthm来解决.使用一个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时失败了.

Answer 1

一种观点是,在任何迭代您需要的值仅适用于r/3对r.所以你可以继续丢弃1/3rd数组.

我不熟悉Java,但C++你可以使用double ended queue (deque):

你继续从后面添加双端队列.
什么时候i = 6,你不需要bu[0]和bu[1].所以你从队列的前面弹出两个元素.

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

编辑:同样如评论中所建议的那样,您应该将数据类型更改为较小的数据类型,因为最大步数应为 ( (log N) to base 2)

EDIT2:正如Dukeling所指出的那样,似乎在Java中没有现成的非常适合deque的实现,这不会影响时间复杂度.您可以考虑像C++一样以自己的方式实现它(我听说它是​​作为向量的向量实现的,内部向量的大小与元素的总数相比较小).