LIS回顾

本题是LIS的进阶版本，上周课上老师举了LIS做例子，在解答本题前，先将LIS的代码贴在这里

class Solution {public:    int lengthOfLIS(vector<int>& nums) {        auto n = (int)nums.size();        vector<int> dp(n, 1);        for (int i = 0; i < n; ++i) {            for (int j = 0; j < i; ++j) {                if (nums[j] < nums[i]) {                    dp[i] = max(dp[i], dp[j] + 1);                }            }        }        return *max_element(dp.begin(), dp.end());    }};

LIS最长回升子序列是一道经典的动静布局问题，解DP问题的关键在于定义正确的状态（有最优子结构）并找到正确的状态转移方程，在LIS中，状态转移方程为
$$LIS_j=max(LIS_i)+1,where\ 0\le i<j,\&\& \ nums[i] < nums[j] $$

最长递增子序列的个数

上面思考第637题，求最长递增子序列的个数

要求最长递增子序列的个数，首先要晓得最长子序列的长度，在LIS的代码中，DP数组代表的就是以第i个数结尾的最长子序列的长度。那么遍历一遍DP数组，咱们就能够晓得最长子序列结尾的那个数有多少种抉择，也就是

vector<int> dp;int cnt = 0;int maxlen = *max_element(dp.begin(), dp.end());for(auto d:dp){    if(d == maxlen) cnt ++;}

那么，如果咱们曾经晓得最初一位，那么倒数第二位的取值又有多少种状况呢？这启发我能够应用DFS广度优先搜寻，穷举最长LIS所有可能的状况，代码如下

class Solution {public:int cnt = 0;    int findNumberOfLIS(vector<int>& nums) {        int n = nums.size();        if (n == 0) {            return 0;        }        vector<int> dp(n, 1);        for (int i = 0; i < n; ++i) {            for (int j = 0; j < i; ++j) {                if (nums[j] < nums[i]) {                    dp[i] = max(dp[i], dp[j] + 1);                }            }        }                int maxlen = *max_element(dp.begin(), dp.end());                for(int i = 0; i < n; i++){            if(dp[i] == maxlen){//如果等于maxlen，则进行DFS                DFS(nums, dp, i);            }        }        return cnt;    }    void DFS(vector<int> &nums, vector<int> & dp, int curPos){        int len = dp[curPos];//搜寻进口        if(len == 1) {            cnt += 1;            return;        }        else{//DFS，每次找符合条件的LIS的前一位，因而要记录curPos示意以后位数            for(int i = curPos-1; i >= 0; i--){                if(dp[i] == len-1 && nums[i] < nums[curPos]){                    DFS(nums, dp, i);                }            }            return;        }    }};

不出所料，超时了，这是因为思考DFS面临的复杂度是十分高的，思考一个极其状况，有n个元素的数组，n能够被k整除，从前到后每k个数彼此相等，即$$1,1,...,1,2,2,...,2,...,n/k,n/k,...,n/k$$共\( n \)，从前到后别离是\( k \)个1，\( k \)个2，\( k \)个3，...\( k \)个n/k，此时DFS的工夫复杂度为\( O((n/k)^k) \)，难免会TLE。

动静布局

最长子序列的个数有最优子结构吗？能够应用DP求解吗？答案是必定的。

class Solution {public:int cnt = 0;    int findNumberOfLIS(vector<int>& nums) {        int n = nums.size();        if (n == 0) {            return 0;        }        vector<int> dp(n, 0);        vector<int> pathNum(n, 1);        for (int i = 0; i < n; ++i) {            dp[i] = 1;            pathNum[i] = 1;            for (int j = 0; j < i; ++j) {                if (nums[j] < nums[i]) {                    if(dp[j] + 1 == dp[i]){                        pathNum[i] += pathNum[j];                    }                    else if(dp[j] + 1 > dp[i]){                        pathNum[i] = pathNum[j];                        dp[i]= dp[j] + 1;                    }                }            }        }                int maxlen = *max_element(dp.begin(), dp.end());        for(int i = 0; i < n; i++){            if(dp[i] == maxlen) {                cnt += pathNum[i];            }        }        return cnt;    }};

定义\( pathNum \)数组，\( pathNum[i] \)示意所有以i结尾的最长子序列的个数，在遍历j变量时，保护pathNum数组即可。具体地，如果找到了以i结尾的更长的子序列长度，且以后以j结尾的子序列个数为\( pathNum[j] \)，那么\( pathNum[i] = pathNum[j] \)即可，相当于在以j结尾的子序列前面附加一个\( nums[i] \)。如果以j结尾的子序列长度恰好比以i结尾的子序列长度小1，阐明前一位还有其余抉择，\( pathNum[i]+= pathNum[j] \)。

最初遍历\( pathNum \)数组即可。