C++ | Simple DP | Explained Properly
IntuitionWe are asked to find the largest subset of numbers such that every pair in the subset satisfies the divisibility condition. This resembles the Longest
# Intuition
We are asked to find the largest subset of numbers such that every pair in the subset satisfies the divisibility condition. This resembles the Longest Increasing Subsequence (LIS) problem, but instead of checking if one number is greater than another, we check if one number divides the other. Sorting the array helps ensure that for any number, all its divisors come before it in the list.

# Approach
1.)Sort the input array to ensure divisibility relations can be checked in one direction (i.e., from smaller to larger).
2.)Use recursion with memoization (a DP table dp[i][prev+1]) where i is the current index and prev is the index of the last included element in the subset.
3.)At each step, we decide:
Take the current element if it's divisible by the previous element.
Not take the current element and move to the next.
4.)Store the result in the DP table to avoid recomputation.
5.)After the DP table is filled, reconstruct the subset using the computed results by following the decisions that led to the optimal value.

# Complexity
- Time complexity:
O(n^2)

- Space complexity:
O(n^2)

# Code
```cpp []
class Solution {
public:
    int n;
    vector<int> sNums;
    vector<vector<int>> dp;
    int rec(int i, int prev) {
        if(i >= n) return 0;
        if(dp[i][prev+1] != -1) return dp[i][prev+1];
        int take = 0;
        if(prev == -1 || sNums[i] % sNums[prev] == 0)
            take = 1 + rec(i+1, i);
        int notTake = rec(i+1, prev);
        int res = (take > notTake) ? take : notTake;
        dp[i][prev+1] = res;
        return res;
    }
    void reconstruct(int i, int prev, vector<int>& subset) {
        if(i >= n) return;
        int take = 0;
        if(prev == -1 || sNums[i] % sNums[prev] == 0)
            take = 1 + rec(i+1, i);
        int notTake = rec(i+1, prev);
        if(prev == -1 || sNums[i] % sNums[prev] == 0) {
            if(take >= notTake) {
                subset.push_back(sNums[i]);
                reconstruct(i+1, i, subset);
                return;
            }
        }
        reconstruct(i+1, prev, subset);
    }
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if(nums.empty()) return {};
        sNums = nums;
        sort(sNums.begin(), sNums.end());
        n = sNums.size();
        dp.assign(n, vector<int>(n+1, -1));
        rec(0, -1);
        vector<int> ans;
        reconstruct(0, -1, ans);
        return ans;
    }
};


```
['C++']