algorithm - 乘/加初始数字以获得目标数字

Question

假设我有一个目标号码 n 例如5，我总是从数字 1 开始，我必须 *2 或 *3 或 +1 直到我到达 n。所以在这种情况下，我会 *2 两次，然后 +1 得到 5。

我应该找到达到目标值的最少操作次数。我看到一个类似的问题是 posted但这需要固定数量的步骤，而我必须找出最少的步骤。关于如何解决这个问题，有什么提示吗？

这是一道作业题。

Answer 1

它可以被视为搜索或DP问题(是的，本质上它们都与状态转换有关), 重点是定义搜索状态条件，假设n是正的，这里我们定义f[i] = inf, inf is a really large integer表示数字 i无法访问，f[i] = k, k >= 0表示数字 i至少可以在 k 内到达步骤。

如果n不是那么大，我们可以用一个数组来存储从 1 到 n 的每个数字的最小步数。最初是f[1] = 0和 f[i] = inf, 2 <= i <= n .如果我们需要输出我们如何获得目标(例如，5 的输出是 1 2 4 5 )，我们可以使用另一个数组 pre存储操作，定义pre[i] = j表示数字 i由编号 j 生产(例如，pre[4] = 2 表示数字 4 由数字 2 产生，因为 2*2=4；pre[3] = 1 表示数字 3 由数字 1 产生，因为 1*3=3):

    int inf = Integer.MAX_VALUE;
    f[1] = 0;
    pre[1] = -1; // pre[i] = -1 means i is the start point
    for(i=2;i<=n;i++) {
        f[i] = inf;
        pre[i] = -1;
    }

    for(int i=1;i<=n;i++) { // since each number is positive so smaller number cannot be produced via larger number, no need to consider > n issue
        if(f[i] == inf) {
            continue;
        }
        if(2*i <= n && f[i] + 1 < f[2*i]) {
            f[2*i] = f[i] + 1;
            pre[2*i] = i; // means number 2*i is produced by number i
        }
        if(3*i <= n && f[i] + 1 < f[3*i]) {
            f[3*i] = f[i] + 1;
            pre[3*i] = i;
        }
        if(i+1 <= n && f[i] + 1 < f[i+1]) {
            f[i+1] = f[i] + 1;
            pre[i+1] = i;
        }
    }

答案是f[n] .

如何输出我们如何获取target，我们使用pre恢复操作的数组:

        curr = n;
        pos = 0;
        ans[pos] = n;
        while(pre[curr] != -1) {
            pos++;
            ans[pos] = pre[curr];
            curr = pre[curr];
        }
        for(int i=pos;i>=0;i--) { // reverse order to output
            System.out.println(ans[i]);
        }

如果n非常大，您可能需要使用优先级队列来维护状态转换，并使用哈希集来维护每个数字的最少步数。