乐趣区

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

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 \)数组即可。

退出移动版