C++ optimized DP beat 99% with explaination


  • 0
    W

    The straightforward DP solution has complexity O(n^2). It can be noted that in inner loop we check all the numbers before the one at outer loop.
    To optimize this, we can use an array of ordered map, and each map at k contains all the <end number of increasing sequence of length k , count> pair. Since all the pairs are sorted by the key.
    For each number N, there are 3 possibilities:

    1. Check the longest increasing sequences (length K) ending at numbers less than N. Then we can get some sequence of length K+1 ending at N. The count of these sequence are the sum of count of those sequences.
    2. The sequence with ending number larger than N will not contribute to longer increasing sequence and can be skipped.
    3. The sequence with ending number equal to N will also be skipped. The count can come from multiple sources and cannot be used directly. To find the increment of new count, we need to repeat step 1 at map dp[K-1]
      The result is the sum of all the counts of the longest increasing sequence.
    class Solution {
    public:
        int findNumberOfLIS(vector<int>& nums) {
            // dp[k] a map is for increasing sequence with length k-1
            // key: ending number, value: count of increasing sequence ending at key number
            vector<map<int,int>> dp;
            int len = nums.size();
            if (len<=1)
                return len;
            dp.push_back(map<int,int>());
            dp[0][nums[0]] = 1;
            for (int i=1; i<len; ++i) {
                int n = nums[i];
                int s = dp.size();
                // looking for chance in increasing the longest length of increasing sequence
                // by searching the longest length first
                for (int j=s-1; j>=0; --j) {
                    auto& m = dp[j];
                    int sum = 0;
                    for (auto& p : m) {
                        if (p.first<n)
                            sum += p.second;
                        else // rest of the ending number >= N, can skip
                            break;
                    }
                    if (sum>0) {
                        if (j==s-1) // check if new longest length is found
                            dp.push_back(map<int,int>());
                        dp[j+1][n] += sum;
                        break;
                    }                 
                }
                // special case (n is the smallest number so far)
                if (n <= dp[0].begin()->first)
                    dp[0][n] += 1;             
            }
            int cnt = 0;
            for(auto p : dp.back())
                cnt += p.second;
            return cnt;
        }
    };
    

Log in to reply
 

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