Beats 99.55% C++ bottom-up DP solution with explanations


  • 0
    S

    dp is two-dimensional,
    each level i of dp are the numbers with i divisors.
    For example, with nums = {1, 2, 3}
    dp[2] = {2, 3}
    dp[1] = {1}
    (dp[0] = {1} for building dp)

    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> dp = {{1}};
        for (int n : nums) {
            for (int i = dp.size() - 1; i >= 0; i--) {
                // If a level consist of a divisor of n, push n to the next level
                for (int j : dp[i]) {
                    if (n % j == 0) {
                        if (dp.size() <= i + 1)
                            dp.push_back(vector<int>());
                        dp[i + 1].push_back(n);
                        break;
                    }
                }
                // If n has been pushed to dp, break to next n
                if (dp.size() > i + 1 && dp[i + 1].back() == n)
                    break;
            }
        }
        // Find all the numbers of the subset with the largest one being the first number in the last level
        vector<int> result;
        int n = dp.back().front();
        for (int i = dp.size() - 1; i > 0; i--) {
            for (int j : dp[i]) {
                if (n % j == 0) {
                    result.insert(result.begin(), n = j);
                    break;
                }
            }
        }
        return result;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.