[C++ DP]Detailed Explanation for Beginners


  • 0
    L

    this problem is very much similar to another well-known DP problem----LIS(longest increasing subsequence). In LIS,we're given a sequence,say, 1 7 3 5 9 4 8,and the target is to get the length of the longest increasing subsequence(in this case 1 3 5 9 is a possible answer,thus 4 is returned) To solve LIS,we can define a state function d[i] to be the length of sequence ending at position i,then d[i]=max(d[j]|j<i && num[j]<num[i])+1,j∈[0,i),the final result would be the largest of d[i]. This equation can be even shorter: d[i]=max(d[i],d[j]+1),if num[j]>num[i],j∈[0,i),in this equation,we've guaranteed that we get the maximum of d[i] every time.
    The solution of the current problem is almost the same as above. We define d[i] to be the length of the longest chain at position i, then there're two possibilities: 1)can't form a larger chain at position i,namely d[i]=d[j],where j is a previous position less than i,2)can form a longer chain,d[i]=d[j]+1. Note that we need to guarantee d[i] is always the maximum, then we have: d[i]=max(d[i],d[j])andd[i]=max(d[i],d[j]+1), that's how we get the state functions.
    The last question: why must we sort the input array? Well,the problem has suggested You can select pairs in any order.,that's to say,in fact,this problem is a LIS problem with flexible order,sort the array guarantees we won't lose any possible solution.

    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            //define dp[i]:the maximum chain we can get at position i
            //our goal:get d[totol_length-1](the final position)
            //dp[i]=max(dp[i],dp[j]), for j in range [0,i), if pairs[i][0]<=pairs[j][1]
            //dp[i]=max(dp[i],dp[j]+1), for j in range [0,i), if pairs[i][0]>pairs[j][1]
            //border:dp[0]=1
            //NOTE:we must sort the array
            int len=pairs.size();
            vector<int>dp(len,0);
            sort(pairs.begin(),pairs.end(),cmp);
            dp[0]=1;
            for(int i=0;i<len;i++){
                for(int j=0;j<i;j++){
                    if(pairs[i][0]<=pairs[j][1])
                        dp[i]=max(dp[i],dp[j]);
                    else
                        dp[i]=max(dp[i],dp[j]+1);
                }
            }
            return dp[len-1];
        }
        //sort according to the first column, i.e. the first number in each pair
        static bool cmp(vector<int>& a, vector<int>& b) {
            return a[0]<b[0];
        }
    };
    

Log in to reply
 

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