Complexity Analysis

Time Complexity: O(N × Target), since each state (ind, T) is computed once.

Space Complexity: O(N × Target) for the DP table, plus O(Target) recursion stack in the worst case.

Tabulation Approach

Algorithm

To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization. We can initialize it as 0.

First, we need to initialize the base conditions of the recursive solution.

At ind==0, we are considering the first element, if the target value is divisible by the first coin’s value, we set the cell's value as 1 or else 0.
Next, we are done for the first row, so our ‘ind’ variable will move from 1 to n-1, whereas our ‘target’ variable will move from 0 to ‘T’. We will set the nested loops to traverse the dp array.
Inside the nested loops, we will apply the recursive logic to find the answer of the cell.
When the nested loop execution has ended, we will return dp[n-1][T] as our answer.

Code