关于c++:Leetcode-637-最长递增子序列的个数

本题是 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 $数组即可。

LIS 回顾

最长递增子序列的个数

动静布局