I get to encounter problems of this kind and when I think that their solution is using dp, either the given value of n turns out to be too large or one of the operations consumes too many recursive function calls. Is there any general way to solve such problems or initial approach one should start thinking?

1. Codeforces Problem 1485A
2. Add and Divide This problem is of 30-day February 2021 challenge Week 3. Requires login to view problem.
3. SPOJ MST1 This problem has n<=1e7, i.e. can be solved using O(n) dp but what if n was upto 1e9 like in this problem.

I also thought of using BFS as it can give me the minimum number of steps to reach the goal but it did not work in general.