[Java/C++] Simple dp solution with explanation


  • 20

    The idea is to use two arrays len[n] and cnt[n] to record the maximum length of Increasing Subsequence and the coresponding number of these sequence which ends with nums[i], respectively. That is:

    len[i]: the length of the Longest Increasing Subsequence which ends with nums[i].
    cnt[i]: the number of the Longest Increasing Subsequence which ends with nums[i].

    Then, the result is the sum of each cnt[i] while its corresponding len[i] is the maximum length.

    Java version:

    public int findNumberOfLIS(int[] nums) {
            int n = nums.length, res = 0, max_len = 0;
            int[] len =  new int[n], cnt = new int[n];
            for(int i = 0; i<n; i++){
                len[i] = cnt[i] = 1;
                for(int j = 0; j <i ; j++){
                    if(nums[i] > nums[j]){
                        if(len[i] == len[j] + 1)cnt[i] += cnt[j];
                        if(len[i] < len[j] + 1){
                            len[i] = len[j] + 1;
                            cnt[i] = cnt[j];
                        }
                    }
                }
                if(max_len == len[i])res += cnt[i];
                if(max_len < len[i]){
                    max_len = len[i];
                    res = cnt[i];
                }
            }
            return res;
        }
    

    C++ version: (use vector<pair<int, int>> dp to combine len[] and cnt[])

        int findNumberOfLIS(vector<int>& nums) {
            int n = nums.size(), res = 0, max_len = 0;
            vector<pair<int,int>> dp(n,{1,1});            //dp[i]: {length, number of LIS which ends with nums[i]}
            for(int i = 0; i<n; i++){
                for(int j = 0; j <i ; j++){
                    if(nums[i] > nums[j]){
                        if(dp[i].first == dp[j].first + 1)dp[i].second += dp[j].second;
                        if(dp[i].first < dp[j].first + 1)dp[i] = {dp[j].first + 1, dp[j].second};
                    }
                }
                if(max_len == dp[i].first)res += dp[i].second;
                if(max_len < dp[i].first){
                    max_len = dp[i].first;
                    res = dp[i].second;
                }
            }
            return res;
        }
    

  • 0

    Hope your advice!


  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

  • 0

    @larrywang2014 Sorry! I modified the title.


  • 0
    R
    This post is deleted!

  • 0
    M

    @Hao-Cai said in [Java/C++] Simple dp solution with explanation:

    Thanks for sharing,
    one point I don't understand is that,
    if(len[i] == len[j] + 1)cnt[i] += cnt[j];
    why it must be the condition len[i] == len[j] + 1
    I'm wondering why len[i] > len[j] doesn't work?


  • 3

    @mycoy len[i] == len[j] + 1 means that you find another subsequence with the same length of LIS which ends with nums[i]. While len[i] > len[j] + 1 means that you find a subsequence, but its length is smaller compared to LIS which ends with nums[i].


  • 0
    Q

    @Vincent-Cai said in [Java/C++] Simple dp solution with explanation:

    @mycoy len[i] == len[j] + 1 means that you find another subsequence with the same length of LIS which ends with nums[i]. While len[i] > len[j] + 1 means that you find a subsequence, but its length is smaller compared to LIS which ends with nums[i].

    pretty clear! thanks!


  • 0
    J

    @Vincent-Cai
    For the input sequence {1,2,3,4,5,3,4}, even though the result is correct which is 1, I was expecting cnt[6] to be equal to 1 but it is 2.

    Why is cnt[5] not equal to cnt[6]? I am missing something.
    Please clarify.

    Thanks.


  • 0

    @jainchethan87 There are two LIS which ends with nums[6], which are [nums[0], nums[1], nums[2], nums[6]] and [nums[0], nums[1], nums[5], nums[6]]. You have nums[2] = nums[5] = 3 here.


  • 0
    J

    @Vincent-Cai
    Missed it, Thanks.


Log in to reply
 

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