If a problem is hard, try solving a simpler version. Here, how to build n from atoms '1', '+' and '*' with a minimal number of 1's.
Make one observation. Suppose an optimal expression for n contains an expression for some smaller number m. Then that expression for m is optimal. Why? If it weren't, we could replace it with a better one, and so improve the expression for n. Contradiction.
Aha! This means we can attack the problem with dynamic programming. Assuming we have optimal expressions for all numbers smaller than n, we can deduce an optimal expression for n. How? The expression for n must end either with addition
(n-1) + 1 or with multiplication
d * (n/d) where d divides n. Inserting optimal expressions for n-1 and n/d , we compute the cost of the expressions for n, and choose the cheapest.
best = MinDict() # optimal expression by number best = (1, "1", False) # cost, expression, needs brackets