Minimum Elements - DP on Subsequence

Problem Link:

https://www.codingninjas.com/studio/problems/minimum-elements_3843091?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf

My approach:

Code:

Memoization:

// TIME COMPLEXITY : O(N^2)
// SPACE COMPLEXITY : O(N*X) + Auxiliary stack space
int helper(vector<int> &num, int i, int x, vector<vector<int>> &dp){

    if(i==0){
        if(x%num[i]==0){
            return x/num[i];
        }
        return 1e9;
    }

    if(dp[i][x]!=-1){
        return dp[i][x];
    }

    int notTake = helper(num,i-1,x,dp);
    int take = INT_MAX;
    if(x>=num[i]){
        take = 1+helper(num,i,x-num[i],dp);
    }

    dp[i][x] = min(notTake, take);
    return min(notTake,take);
}

int minimumElements(vector<int> &num, int x)
{
    // Write your code here.
    int n = num.size();
    vector<vector<int>> dp(n, vector<int>(x+1,-1));

    int ans = helper(num,n-1,x,dp);
    if(ans==1e9){
        return -1;
    }
    return ans;
}

Tabulation:

// TIME COMPLEXITY : O(N^2)
// SPACE COMPLEXITY : O(N*X) 

int minimumElements(vector<int> &num, int x)
{
    // Write your code here.
    int n = num.size();
    vector<vector<int>> dp(n, vector<int>(x+1,1e9));

    for(int i=0;i<n;i++){
        dp[i][0] = 0;
    }

    for(int i=1;i<=x;i++){
        if(i%num[0]==0){
            dp[0][i] = i/num[0];
        }
    }

    for(int i=1;i<n;i++){
        for(int j=1;j<=x;j++){
            int notTake = dp[i-1][j];
            int take = 1e9;
            if(num[i]<=j){
                take = 1+dp[i][j-num[i]];
            }

            dp[i][j] = min(take,notTake);
        }
    }

    if(dp[n-1][x]==1e9){
        return -1;
    }
    return dp[n-1][x];
}