Time Complexity depends upon the following factors:

1. The number of dp states(=S)
   
2. The average number of states a given state depends upon (=T) the transition time.

Overall Space complexity is usually (though can be optimised) O(S)

Overall Time complexity is usually O(S*T)

For Fibonacci

1. To calculate fib(N), you have N states in total(dp1 dp2 .... dpN)

2. Each state depends upon 2 other states.

So using above formula : O(N)*O(1) = O(N)

UPD: I'll illustrate 2 examples.

Ex1 : Say for the solution to some problem, the recurrence is :
dp[i] = max { v[i] + dp[j] } for all j < i.
We want to calculate dp[N] and we know dp[0] = x.
Total states = N+1 = O(N). ith state depends upon i-1 states.
Average number of states a state depends upon = (0 + 1 + 2 + ... + N-1)/(N+1) ~ N^2/N = O(N)

So overall Time complexity = O(N)*O(N) = O(N^2), space complexity = O(N).

Ex2 : dp[i][j] = sum dp[i-1][k] over all k from 0 to j — 1 We want dp[N][M] and we know dp[0][x] = 1 and dp[i][0] = i.

Total states = N*M. On similar lines, the transition time here is O(j) for some state dp[x][j].
There are N states in which j = 0, N in which j = 1 and so on till N states in which j = M.
Average number of states a state depends upon = (N*0 + N*1 + N*2 + ... + N*M)/(N*M) = N*(1 + 2 + .. + M)/(N*M) ~ (NM^2)/(NM) = O(M)

Overall time complexity = O(NM)*(M) = O(NM^2)
Space complexity = O(NM)

Space complexity can be easily optimized to O(M) as you only need to store dp[i-1][j] in the memory.