一步的最小步骤

问题陈述 ：

在正整数上，您可以执行以下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。我不想增加我的堆空间。是否有人使用更少的空间解决方案？

请注意这个问题不能用贪婪的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 。 所以你可以继续丢弃arrays的1/3rd 。

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

你不断从后面添加双端队列。
当i = 6 ，您不需要bu[0]和bu[1] 。 所以你从队列的前面弹出两个元素。

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

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

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

Answer 2

更新：这是更新的代码，我实际测试了一些，我相信n从1到100000得到相同的答案。我将离开下面的原始答案供参考。 缺陷是MAX_INT的“聪明”使用。 我忘了在某些情况下我会跳过-1的可能性，但数字也不能被2或3整除。这解决了通过返回null来表示“这条路径无意义进一步探索”。

 public static int steps(int n) { return steps(n, 0); } private static Integer steps(int n, int consecutiveMinusOnes) { if (n <= 1) { return 0; } Integer minSteps = null; if (consecutiveMinusOnes < 2) { Integer subOne = steps(n - 1, consecutiveMinusOnes + 1); if (subOne != null) { minSteps = 1 + subOne; } } if (n % 2 == 0) { Integer div2 = steps(n / 2, 0); if (div2 != null) { if (minSteps == null) { minSteps = div2 + 1; } else { minSteps = Math.min(minSteps, 1 + div2); } } } if (n % 3 == 0) { Integer div3 = steps(n / 3, 0); if (div3 != null) { if (minSteps == null) { minSteps = div3 + 1; } else { minSteps = Math.min(minSteps, 1 + div3); } } } return minSteps; } 

我相信这可行，但我没有certificate。 这个算法是基于这样的想法，即减去1的唯一原因是让你更接近可被2或3整除的数字。因此，你真的不需要将减去一步的步骤应用两次以上连续，因为如果k％3 == 2，则k - 2％3 == 0并且你可以除以3。 再减去一次将是一种努力的浪费（你也会通过至少一个偶数，所以最好的两步机会将会出现）。 这意味着自上而下的递归方法，如果您想要，您可以混合使用一些记忆：

 public static int steps(n) { return steps(n, 0); } private static int steps(int n, int consecutiveMinusOnes) { if (n <= 1) { return 0; } int minSteps = Integer.MAX_VALUE; if (consecutiveMinusOnes < 2) { minSteps = 1 + steps(n - 1, consecutiveMinusOnes + 1); } if (n % 2 == 0) { minSteps = Math.min(minSteps, 1 + steps(n / 2, 0)); } if (n % 3 == 0) { minSteps = Math.min(minSteps, 1 + steps(n / 3, 0)); } return minSteps; } 

免责声明：正如我上面所说，我还没有certificate这种方法有效。 我还没有测试过这个特定的实现。 我也没有做过记忆化的东西，因为我很懒。 无论如何，我希望即使这不起作用，它也会给你一些关于如何修改你的方法的想法。

Answer 3

这工作:)

 import java.util.Scanner; public class MinimumStepToOne { public static void main(String[] args){ Scanner sscan = new Scanner(System.in); System.out.print("Give a no:" + " "); int n = sscan.nextInt(); int count = 0; for(int i = 0; n > 1; i++){ if(n%2 == 0){n /= 2; count++;} else if(n%3 == 0){ n /= 3; count++;} else { n -= 1; count++;} } System.out.println("your no is minimized to: " + n); System.out.println("The min no of steps: " + count); } }