We all know F(n) = F(n-1) + F(n-2) is an easy example. We can compute this by using DP.But what about F(n) = F(n-1) + k, we could compute this by tabulation but would you still call it DP?Also, are there any recurrences that cannot be computed using tabulation?Is there a general theory surrounding the kind if recurrences that can be effectively computed using tabulation / DP.Thanks in advance.
What kinds of recurrence relations can be involved in a tabulation solution?
algorithms;recurrence relation;memoization