java - 归零二

Question

这是问题:

You are given Q queries. Each query consists of a single number N . You can perform any of the operations on in each move:

1. If we take 2 integers a and b where N=a*b (a ,b cannot be equal to 1), then we can change N=max(a,b)

2. Decrease the value of N by 1 .

Determine the minimum number of moves required to reduce the value of to .

Input Format

The first line contains the integer Q.
The next Q lines each contain an integer,N .

Output Format

Output Q lines. Each line containing the minimum number of moves required > to reduce the value of N to 0.

我已经编写了以下代码。这段代码给出了一些错误的答案，并且给出了 time limit exceeded error 。你能说出我的代码中存在哪些错误吗？我在这里做错了什么？
我的代码:

public static int downToZero(int n) {
// Write your code here
    int count1=0;
    int prev_i=0;
    int prev_j=0;
    int next1=0;
    int next2=Integer.MAX_VALUE;
    
    if (n==0){
        return 0;
    }

    while(n!=0){
        if(n==1){
            count1++;
            break;
        }
        next1=n-1;
        outerloop:
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if (i*j==n){
                    if (prev_i ==j && prev_j==i){
                        break outerloop;
                    }
                    if (i !=j){
                        prev_i=i;
                        prev_j=j;
                    }
                    int max=Math.max(i,j);
                    if (max<next2){
                        next2=max;
                    }
                       
                }
                
            }
        }
        n=Math.min(next1,next2);
        count1++;
    }
    return count1;
}

这是为我们编码的部分:

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        for (int qItr = 0; qItr < q; qItr++) {
            int n = Integer.parseInt(bufferedReader.readLine().trim());

            int result = Result.downToZero(n);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedReader.close();
        bufferedWriter.close();
    }
}

例如:它不适用于号码 7176 ....

Answer 1

要探索所有解树并找到全局最优解，我们必须选择最好的结果 来自所有可能的除数对 来自 solution(n-1)我对 Java 的奇怪翻译 (ideone)使用自下而上的动态编程来加快执行速度。
我们计算值 i 的解来自 1至 n ，它们被写入 table[i] .
首先我们将结果设置为 1 + best result for previous value (table[i-1]) .
然后我们分解 N进入 所有对除数并检查是否使用已经计算的结果来获得更大的除数 table[d]给出更好的结果。
最后我们将结果写入表中。
请注意，我们可以计算table一次用完 Q查询。

class Ideone
{
    public static int makezeroDP(int n){
       int[] table = new int[n+1];
       table[1] = 1; table[2] = 2; table[3] = 3;
       int res;
       for (int i = 4; i <= n; i++) {
          res = 1 + table[i-1];
          int a = 2;
          while (a * a <= i) {
             if (i % a == 0)
                res = Math.min(res, 1 + table[i / a]);
             a += 1;
          }
          table[i] = res;
       }
       return table[n];
    }
     
    public static void main (String[] args) throws java.lang.Exception
    { 
        int n = 145;//999999;
        System.out.println(makezeroDP(n));
    }
}

旧部分
简单的实现(抱歉，在 Python 中)给出了答案 7为 7176

def makezero(n):
    if n <= 3:
        return n
    result = 1 + makezero(n - 1)
    t = 2
    while t * t <= n:
        if n % t == 0:
            result = min(result, 1 + makezero(n // t))
        t += 1
    return result

在 Python 中，需要设置递归限制或更改算法。现在使用备忘，正如我在评论中所写)。

t = [-i for i in range(1000001)]
def makezeroMemo(n):
    if t[n] > 0:
        return t[n]
    if t[n-1] < 0:
        res = 1 + makezeroMemo(n-1)
    else:
        res = 1 + t[n-1]
    a = 2
    while a * a <= n:
        if n % a == 0:
            res = min(res, 1 + makezeroMemo(n // a))
        a += 1
    t[n] = res
    return res

自底向上的表动态规划。没有递归。

def makezeroDP(n):
    table = [0,1,2,3] + [0]*(n-3)
    for i in range(4, n+1):
        res = 1 + table[i-1]
        a = 2
        while a * a <= i:
            if i % a == 0:
                res = min(res, 1 + table[i // a])
            a += 1
        table[i] = res
    return table[n]