Complexity Analysis:

Time Complexity: O(N*W), where N is the size of the array and W is the capacity of the knapsack. There are N*W states therefore at max ‘N*W’ new problems will be solved.

Space Complexity:O(N*W) + O(N), We are using a recursion stack space(O(N)) and a 2D array ( O(N*W)).1e:T47b8,

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Declare a dp array of size [n][W+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The size of the input array is ‘N’, so the index will always lie between ‘0’ and ‘n-1’. The capacity can take any value between ‘0’ and ‘W’. Therefore 2D dp array(dp[n][W+1]) is needed. Set its type as int and initialize it as 0.
Setting Base Cases in the Array: In the recursive code, our base condition was when ind == 0, it meant we were at the first item, so in that case were checking whether this item’s weight is less than or equal to the current capacity W, if it was, we were simply returning its value (val[0]) else we were returning 0. So, will set the same value for 'ind' = 0 in the dp array.
Iterative Computation Using Loops: Initialize two nested for loops to traverse the dp array. First loop will run from 1 to n-1 as we are done for the ind = 0 for the base case and the second loop will run from 0 to 'W'.
Now, following the same logic as discussed in the recursive approach, set the value of each cell in the 2D dp array. Instead of recursive calls, use the dp array itself to find the values of intermediate calculations.
Returning the answer: At last dp[n-1][W] will hold the solution after the completion of whole process, as we are doing the calculations in bottom-up manner.

#include <bits/stdc++.h>
using namespace std;

class Solution{
public:  
    // Function to solve the 0/1 Knapsack pro