Can we figure out the complexity of a DP solution (recursion + memoization, ie top-down) for a particular problem.
This might look to be a very general question. What I am implying is, if a particular problem cannot be thought up easily in a bottom up manner (where knowing complexity is easier), then how can we ascertain the complexity of the dp solution.
Fibonacci for example can be calculated via
1. Bottom Up: f[i] = f[i - 1] + f[i - 2]
It is easy to see the complexity would be O(n).
2. Top Down: f(n) = f(n - 1) + f(n - 2)
Recursively, the complexity is O(φⁿ) which will be reduced to O(n) with memoization (by knowing the distinct states).
So, is their always a relation between complexity of top-down and the distinct states/subproblems, which can be figured out?