乘以/添加初始数以获得目标数

Question

假设我有一个目标数n如5,我总是从1号开始,我得*2或*3或+1到它,直到我到达n.所以在这种情况下,我会*2两次,然后+1获得5.

我应该找到达到目标值的最少操作次数.我看到一个类似的问题正在发布,但这需要一定数量的步骤,而我必须找出最少的步骤.有关如何解决这个问题的提示吗？

这是一个家庭作业问题.

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].

如何输出我们如何获得目标,我们使用该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]);
        }

虽然if n非常大,但您可能需要使用优先级队列来维护状态转换,并使用哈希集来维护每个数字的最小步数.