Time Complexity: O(n × n) Each subproblem (i, length) is computed once.

Space Complexity: O(n × n),We use a 2D DP table for memoization.

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, so we will assign its value as (i/wt[0]) * val[0], where i will iterate from 0 to W.
Next, we are done for the first row, so our ‘ind’ variable will move from 1 to n-1, whereas our ‘cap’ variable will move from 0 to ‘W’. 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][W] as our answer.

Code

123456789