Bilibili 9.1笔试，N值乘法分解最小和

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @author bty
 * @date 2022/9/1
 * @since 1.8
 **/
public class Main {
    private static int N=0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

         N = in.nextInt();

        LinkedList<Integer> curRes = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        dfs(N,1,curRes,res);
        if(res.size()==0){
            System.out.println(N);
            return;
        }
        int minSum = Integer.MAX_VALUE;

        for (List<Integer> r : res) {
            int temp = 0;
            for (Integer i : r) {
                temp +=i;
            }
            minSum = Math.min(minSum,temp);
        }
        System.out.println(minSum);

    }
    public static void dfs(int tar, int cur, LinkedList<Integer> curRes, List<List<Integer>> res){
        if(cur>tar){
            return;
        }
        if(cur==tar){
            res.add(new ArrayList<>(curRes));
            return;
        }


        for (int i = 2; i <= N-1; i++) {
            cur *= i;
            curRes.offerLast(i);
            dfs(tar,cur,curRes,res);
            curRes.pollLast();
            cur /=i;
        }
    }

}