一步的最小步骤

问题陈述 :

在正整数上,您可以执行以下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,这个解决方案会抛出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时失败了.