力扣刷题——3177. 求出最长好子序列 II

根据题意，暴力做法不可取，因为至少要对遍历位置之前的位置，以及不同的子序列阈值（跟k对应的那个）做循环。于是就能够想到使用动态规划的手段去解决问题，考虑需要保存的两个状态，当前序列末尾的数字、子序列阈值，设计一个二维的dp数组dp[i][j]，其中i为位置索引，指代当前在nums数组中遍历的位置，j则为子序列阈值。
综上，每次循环递推有如下递推式：
当nums[x] != nums[i]并且j > 0时，dp[i][j] = max(dp[x][j - 1] + 1, dp[i][j])
当nums[x] == nums[i]时,dp[i][j] = dp[x][j] + 1
每次循环枚举所有可能的j值，即0 <= j <= k,以及所有可能的x值，即0 <= x < i。则有实现代码如下：

class Solution
{
public:
    int maximumLength(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(k + 1, -1));
        int res = 1;
        for (int i = 0; i < n; i++)
        {
            dp[i][0] = 1;
            for (int j = 0; j <= k; j++)
            {
                for (int x = 0; x < i; x++)
                {
                    if (nums[i] == nums[x])
                    {
                        dp[i][j] = max(dp[i][j], dp[x][j] + 1);
                    }
                    else
                    {
                        if (j)
                        {
                            dp[i][j] = max(dp[x][j - 1] + 1, dp[i][j]);
                        }
                    }
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
};

但是这样仍然会超时。想到因为dp数组之中的第一维度信息只跟具体的数值有关，跟数值的位置无关，使用哈希表可以减少需要遍历的数据范围，因此有以下实现：

class Solution
{
public:

    int maximumLength(vector<int> &nums, int k)
    {
        int n = nums.size();
        int res = 1;
        unordered_map<int, vector<int>> dp;
        for (int i = 0; i < n; i++)
        {
            vector<int> temVec;
            if (dp.find(nums[i]) == dp.end())
            {
                temVec = vector<int>(k + 1, 0);
                temVec[0] = 1;
            }
            else
            {
                temVec = dp[nums[i]];
            }

            for (auto tem : dp)
            {
                for (int j = 0; j <= k; j++)
                {
                    if (nums[i] == tem.first)
                    {
                        if (dp[tem.first][j])
                            temVec[j] = max(temVec[j], dp[tem.first][j] + 1);
                        res = max(res, temVec[j]);
                    }
                    else
                    {
                        if (j)
                        {
                            if (dp[tem.first][j - 1])
                                temVec[j] = max(dp[tem.first][j - 1] + 1, temVec[j]);
                        }
                    }
                    res = max(res, temVec[j]);
                }
            }
            dp[nums[i]] = temVec;
        }
        return res;
    }
};

结果还是超时。。。使用哈希表，对当nums[x] == nums[i]的情况下优化了计算量，然而还存在大量nums[x] != nums[i]的情况。
实际上对于这种情况，可以绕过重复遍历nums[x]。当遍历到i位置时，如果后面的位置不存在nums[x]，并且dp[nums[x]]中的值均不是目前的最优解，那么可以判断由dp[nums[x]]递推出的值不可能会是最终的答案；假如后面的位置存在nums[x]，那么仍然可以通过维护dp[nums[x]]，保留可能的递推来源。
基于上面这个想法，可以选择开一个数组，单独维护当nums[x] != nums[i]时的最优解，这样就意味着，用基于这个辅助数组递推出来的解可能是最优的，实现代码如下：

class Solution {
public:
    int maximumLength(vector<int> &nums, int k)
    {
        int n = nums.size();
        int res = 1;
        vector<int> sub(k + 1, 0);
        unordered_map<int, vector<int>> dp;
        for (int i = 0; i < n; i++)
        {
            vector<int> temVec;
            if (dp.find(nums[i]) == dp.end())
            {
                temVec = vector<int>(k + 1, 0);
            }
            else
            {
                temVec = dp[nums[i]];
            }

            for (int j = 0; j <= k; j++)
            {
                temVec[j]++;
                if(j)
                {
                    temVec[j] = max(temVec[j], sub[j - 1] + 1);
                }
            }
            dp[nums[i]] = temVec;

            for(int j = 0; j <= k; j++)
            {
                sub[j] = max(sub[j], dp[nums[i]][j]);
                res = max(res, sub[j]);
            }
                
        }
        return res;
    }
};