In memoized version of dp, for example 0/1 knapsack is the time complexity remains same O(N*M) as number of functions call may be more because let’s say until the value of dp[i][j] is calculated there might be multiple function call already made for i,j.
No, it’s the same. If there are multiple calls for dp_{i,j}, then value of dp_{i,j} would be calculated in the first call itself and then for further calls, it will be taken from the memo.
@akshitm16 But in case of multiple calls to same dp[i][j], if value is calculated in first time, but still those call will be made although it will return if the value is already calculated.?
It some state directly depends on some another state which was already calculated previously, then it’s value will be used directly. We don’t have to recalculate that another state. The number of calls to some state will be same in recursive approach as well as the iterative one. The order in which states are called maybe different.