通过 3 个特定操作从 1 到 n 的高效算法

Question

问题：

Given those 3 valid operations over numbers and an integer n:

add 1 to the number

multiply the number by 2

multiply the number by 3

describe an efficient algorithm for the minimal number of operations of getting from 1 to n with the 3 operations mentioned above.

For example for n = 28 the answer is 4 : 1 * 3 * 3 * 3 + 1 = 27 + 1 = 28.

我在java写了下面的代码，对于num>=1000，需要很多时间才能结束。你能帮我理解错在哪里吗w.r.t。效率。我正在尝试制作一种更有效的算法来解决问题。请帮忙

public static int ToN(int num){
    return to(1,num);
}
public static int to(int x,int y){
    if (x==y)
        return 0;
    if (x>y)
        return y;
    return Math.min(Math.min(to(x+1,y),to(x*2,y)),to(x*3,y))+1;
}

Answer 1

动态规划

使用以前计算的结果计算新的结果。这使得解决方案是线性的，而不是你的情况下的指数。

Python 程序

import sys
n = int(raw_input())
dp = [sys.maxint]*(n+1)
dp[1] = 1

for i in xrange(2, n+1):
    dp[i] = dp[i-1]+1
    if i%2==0:    dp[i] = min(dp[i], dp[i/2]+1)
    if i%3==0:    dp[i] = min(dp[i], dp[i/3]+1)

print dp[n]

Answer 2

你的解决方案很慢，因为你没有缓存以前计算的结果（i < num 的最佳解决方案），并且你每次都重新计算它们。这使得它在指数时间内工作，因为每次调用 toN 函数都会产生 3 个其他调用，依此类推

public static int ToN(int num){
    int[] opsRequired = new int[num+1];
    opsRequired[1] = 1;
    for (int i=2; i <= num; i++) {
         opsRequired[i] = opsRequired[i-1];
         if (i % 2 == 0)
             opsRequired[i] = Math.min(opsRequired[i], opsRequired[i/2]);
         if (i % 3 == 0)
             opsRequired[i] = Math.min(opsRequired[i], opsRequired[i/3]);
         opsRequired[i]++;
    }
}

Answer 3

你可以反思两件事：

1）为什么你的递归方法需要两个参数？如果问题涉及始终从 1 移动到 n，我们可以只用一个参数来解决。请注意，在递归时，您按原样传递 y（并且您也不会在方法中对 y 的值进行操作）。这通常表明参数本身是多余的。
2) 优化参数后，我们现在可以 memoize 解决方案。这会大大加快你的方法。

Answer 4

对于正整数，乘以 3 总是比乘以 2 快，后者总是比加 1 快。所以算法很简单。

if x == y return 0
if x <= y/3 return 1 + to(x*3,y)
if x <= y/2 return 1 + to(x*2,y)
return y-x

通过 3 个特定操作从 1 到 n 的高效算法

Efficient algorithm for getting from 1 to n with 3 specific operations

algorithm

dynamic-programming

number-theory

动态规划