【动态规划】子序列问题（二）

📝前言说明：

• 本专栏主要记录本人的动态规划算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

1218. 最长定差子序列

题目链接：https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/

优质解

思路：

• 像解递增一样解这道题肯定是超时的，时间复杂度太高了
• 我们要利用题目的difference信息，我们可以通过difference信息直接计算出前一个数的值
• 然后准确找到前一个数的下标，把dp[i]更新
• 怎么快速找前一个数呢？利用哈希表

代码（直接在哈希表里面dp）：

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        unordered_map<int, int> hash; // 存储{arr[i], dp[i]}
        int ans = 1;
        hash.insert({arr[0], 1}); // 初始化插入第一个元素
        for(int i = 1; i < n; i++)
        {
            int front = arr[i] - difference;
            hash[arr[i]] = hash.find(front) != hash.end()? hash[front] + 1 : 1;
            ans = max(hash[arr[i]], ans);
        }
        return ans;
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

873. 最长的斐波那契子序列的长度

题目链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/description/

优质解

思路：

• 因为一个斐波那契数列依赖于三个数
• 像之前的题目，如果我们知道nums[i]，则我们可以根据遍历i前的所有nums[j]来确定子序列的样子
• 但是这里，我们仅靠i + 遍历，是无法确定斐波那契数列的样子
• 所以我们需要：i + j + 遍历
• dp[i][j]：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，最长的斐波那契子序列的长度（ j < i ）
• 状态转移方程
  • 先找到一个nums[k] == nums[i] - nums[j]（并且这个k < j）
  • dp[i][j] = dp[j][k] + 1
• 初始化：dp的所有值为 2
• 返回值：dp里面最大的，如果最大的是 2 则返回 0

代码：

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) 
    {
        int n = arr.size();
        if(n < 3) return 0;
        unordered_map<int, int> hash; // {arr[i], 下标} 方便查找元素
        for(int i = 0; i < n; i++) hash[arr[i]] = i; // 此题没有重复元素
        int ans = 2;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        for(int i = 2; i < n; i++)
        {
            for(int j = i - 1; j >= 1; j--)
            {
                int a = arr[i] - arr[j];
                if(a < arr[j] && hash.find(a) != hash.end())
                {
                    dp[i][j] = dp[j][hash[a]] + 1;
                }
                ans = max(dp[i][j], ans);
            }
        }
        return ans > 2? ans : 0;
    }
};

时间复杂度：$O(n^2)$
空间复杂度：$O(n^2)$

1027. 最长等差数列

题目链接：https://leetcode.cn/problems/longest-arithmetic-subsequence/description/

优质解

思路：

• 因为会有重复元素，只能一遍dp，一遍加{元素，下标}

代码：

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) 
    {
        int n = nums.size();
        if(n < 3) return n;
        unordered_map<int, int> hash; // {元素, 下标}
        hash[nums[0]] = 0;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ans = 2;
        for(int j = 1; j < n - 1; j++) // 先枚举倒数第二个，因为要加入dp
        {
            for(int i = j + 1; i < n; i++)
            {
                int a = 2 * nums[j] - nums[i];
                if(hash.find(a) != hash.end()) // hash[a] < j 天然满足理论，因为每次往hash表里加的都是前[0, j - 1]的元素
                {
                    dp[i][j] = dp[j][hash[a]] + 1;
                }
                ans = max(ans, dp[i][j]);
            }
            // 放在后面加，因为往前找元素的时候，找的是倒数第二个元素之前的元素
            // 为什么可以覆盖前面同元素的下标？（因为，我们可以只考虑最后一个，因为最后一个的“最长子序列”最长）
            hash[nums[j]] = j; 
        }
        return ans;
    }
};

时间复杂度：$O(n^2)$
空间复杂度：$O(n^2)$

446. 等差数列划分 II - 子序列

题目链接：https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/

优质解

思路：

• 看上去感觉跟前面的题目一样，但是怎么处理重复元素的问题呢？
• 这里要统计全部，而不是只关注最后一个
• 所以我们可以用一个vector来记录所有下标，提前把所有元素与下标数组绑定
• 在判断是否为前驱元素的时候，多加一个下标判断

代码：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        int n = nums.size();
        unordered_map<long long, vector<int>> hash; // {元素, 下标数组}
        for(int i = 0; i < n; i++)
            hash[nums[i]].push_back(i);
        vector<vector<int>> dp(n, vector<int>(n, 0));
        int ans = 0;
        for(int j = 1; j < n - 1; j++)
        {
            for(int i = j + 1; i < n; i++)
            {
                long long num = 2 * (long long)nums[j] - nums[i]; // 会溢出，先强转nums[i]
                if(hash.find(num) != hash.end())
                {
                    for(auto k: hash[num])
                    {
                        // 为什么是：+= 不是 = ？
                        // 因为：以 j,i为结尾的数组基于多个 以 k, j结尾的数组
                        if(k < j) dp[i][j] += dp[j][k] + 1;
                    }
                }
                ans += dp[i][j];
            }
        }
        return ans;
    }
};

时间复杂度：$O(n^3)$，最坏
空间复杂度：$O(n^2)$

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！