down-to-zero-ii

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

1: If we take 2 integers  and  where , , then we can change 

2: Decrease the value of  by .

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

Input Format

The first line contains the integer .

The next  lines each contain an integer, .

Constraints

Output Format

Output  lines. Each line containing the minimum number of moves required to reduce the value of  to .

Sample Input

2
3
4

Sample Output

3
3

Explanation

For test case 1, We only have one option that gives the minimum number of moves.

Follow  3->  2->  1-> 0. Hence,  moves.

For the case 2, we can either go  4-> 3 -> 2 -> 1 -> 0 or  4-> 2 ->  1->0 . The 2nd option is more optimal. Hence,  moves.

动态规划，分析同：【动态规划】CMB2 小招喵跑步

public static int downToZero(int n) {
        if (n == 0) return 0;
        
        // DP array to store minimum moves for each number
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            // Option 1: Subtract 1
            dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            
            // Option 2: For each factor pair (a, b) where a * b = i and a > 1, b > 1
            // Move to max(a, b) which is the larger factor
            for (int a = 2; a * a <= i; a++) {
                if (i % a == 0) {
                    int b = i / a;
                    int maxFactor = Math.max(a, b);
                    dp[i] = Math.min(dp[i], dp[maxFactor] + 1);
                }
            }
        }
        
        return dp[n];
    }

以上dp针对n很大的时候超时，所以用BFS 队列优化。

public static int downToZero(int n) {
        if (n == 0) return 0;
        
        Queue<Integer> queue = new LinkedList<>();
        int[] moves = new int[n + 1];
        Arrays.fill(moves, -1);
        
        queue.offer(n);
        moves[n] = 0;
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            if (current == 0) {
                return moves[current];
            }
            
            // Option 1: Subtract 1
            int next = current - 1;
            if (next >= 0 && moves[next] == -1) {
                moves[next] = moves[current] + 1;
                queue.offer(next);
            }
            
            // Option 2: For each factor pair, move to the larger factor
            for (int a = 2; a * a <= current; a++) {
                if (current % a == 0) {
                    int b = current / a;
                    int maxFactor = Math.max(a, b);
                    
                    if (maxFactor <= n && moves[maxFactor] == -1) {
                        moves[maxFactor] = moves[current] + 1;
                        queue.offer(maxFactor);
                    }
                }
            }
        }
        
        return moves[0];
    }