Does it have another optimal solution for this problem?

#1

https://cses.fi/problemset/task/1623/
this is the problem that i’m currently working with, i know how to solve it using recursion and bitmask and i’ve already AC it. But i have a question whether it exist more optimal solution, i’m thinking about dp or another greedy way but i’m still stuck because i could figure out the fully way to solve them.

#2

You could use meet in the middle to effectively divide n by 2. But the solution would still be exponential in n.

#3

I was thinking this problem could use dp but why can’t it use dp ?