【动态规划】子序列问题

一、最长递增子序列

题目描述：

思路讲解：
本道题需要我们计算最长严格递增子序列的长度，最长严格递增子序列是从数组中选取部分元素，保持元素顺序不变且严格递增的最长序列，问题可拆解为：以第 i 个元素为结尾的最长递增子序列长度，取决于所有在 i 之前且值小于 nums [i] 的元素所对应的最长子序列长度的最大值加 1。以下是具体思路：

1. 状态表示：dp[i] 表示以第 i 个元素为结尾的最长严格递增子序列的长度
2. 状态转移方程：
   • 遍历所有 j < i（即 i 之前的元素），若 nums[i] > nums[j]（满足严格递增），则 dp[i] = max(dp[i], dp[j] + 1)
   • 如果第 i 个元素大于第 j 个元素，那么以 i 为结尾的子序列可以在以 j 为结尾的子序列基础上增加一个元素（即 nums [i]），此时长度为 dp [j] + 1，取所有可能的最大值作为 dp [i] 的值
3. 初始化：
   • 所有 dp[i] 初始化为 1：因为每个元素自身可以构成一个长度为 1 的递增子序列（至少包含自身）
4. 填写 DP 表与结果保存：
   • 按照从左到右的顺序，外层循环从第 1 个元素遍历到最后一个元素（i=1 到 i=n-1），内层循环遍历 i 之前的所有元素（j=0 到 j=i-1），根据状态转移方程更新 dp [i]
   • 同时维护变量 ret，实时记录遍历过程中出现的最大 dp 值（即整个数组中最长递增子序列的长度）
5. 结果返回：
   • 遍历结束后，ret 中存储的就是最长严格递增子序列的长度，直接返回即可

编写代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n,1);

        int ret = dp[0];
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                if(nums[i] > nums[j])
                {
                    dp[i] = max(dp[i],dp[j] + 1);
                }
            }
            ret = max(ret,dp[i]);
        }

        return ret;
    }
};

二、摆动序列

题目描述：

思路讲解：
本道题需要我们找到摆动序列的最长子序列的长度 ，摆动序列要求连续数字的差值严格在正负之间交替，需要区分两种摆动模式，这里我们定义两个状态数组分别记录以每个位置为结尾的两种摆动模式的最长子序列长度。以下是具体思路：

1. 状态表示：
   • f[i] 以第 i 个元素结尾中所有子序列，最后一个位置呈现为“上升”趋势的最长摆动序列的长度
   • g[i] 以第 i 个元素结尾中所有子序列，最后一个位置呈现为“下降”趋势的最长摆动序列的长度
2. 状态转移方程：
   • 若 nums[i] > nums[j]（当前差值为正）：
     • 当前必须呈现“上升”趋势才能形成交替，故 f[i] = max(f[i], g[j] + 1)（在 j 结尾的负差值子序列基础上增加当前元素）
   • 若 nums[i] < nums[j]（当前差值为负）：
     • 当前必须呈现“下降”趋势才能形成交替，故 g[i] = max(g[i], f[j] + 1)（在 j 结尾的正差值子序列基础上增加当前元素）
   • 若 nums[i] == nums[j]：差值为 0，不满足摆动条件，不更新状态
3. 初始化：
   • 所有位置初始值为 1：f[i] = g[i] = 1（单个元素自身是长度为 1 的摆动序列）
4. 填写 DP 表与结果保存：
   • 按照从左到右的顺序，外层循环从第 1 个元素遍历到最后一个元素（i=1 到 i=n-1），内层循环遍历 i 之前的所有元素（j=0 到 j=i-1），根据元素大小关系更新 f[i] 和 g[i]
   • 维护变量 ret，实时记录遍历过程中 f[i] 和 g[i] 的最大值（即最长摆动子序列长度）
5. 结果返回：
   • 遍历结束后，ret 中存储的就是最长摆动子序列的长度，直接返回即可

编写代码：

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();

        vector<int> f(n,1) , g(n,1);

        int ret = f[0];
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                if(nums[i] > nums[j])
                {
                    f[i] = max(f[i],g[j] + 1);
                }
                else if(nums[i] < nums[j])
                {
                    g[i] = max(g[i],f[j] + 1);
                }
            }
            ret = max(ret,f[i]);
            ret = max(ret,g[i]);
        }

        return ret;
    }
};

三、最长递增子序列的个数

题目描述：

思路讲解：

本道题需要我们计算数组中最长严格递增子序列的个数，问题可拆解为：对于每个元素，需同时记录以其为结尾的最长递增子序列长度，以及形成该长度的子序列数量。

1. 状态表示：
   • len[i] 表示以第 i 个元素为结尾的最长严格递增子序列的长度
   • count[i] 表示以第 i 个元素为结尾，且长度为len[i]的严格递增子序列的个数
2. 状态转移方程：
   • 若 nums[i] > nums[j]（满足严格递增）：
     • 若 len[j] + 1 > len[i]：说明找到更长的子序列，更新len[i]为len[j] + 1，同时count[i]继承count[j]（新长度的子序列由 j 对应的子序列扩展而来）
     • 若 len[j] + 1 == len[i]：说明存在新的同等长度的子序列，将count[j]累加到count[i]中（两种途径形成相同长度的子序列）
3. 初始化：
   • 所有 len[i] 初始化为 1：每个元素自身可构成长度为 1 的子序列
   • 所有 count[i] 初始化为 1：每个元素自身构成的子序列只有 1 种（即其本身）
4. 填写 DP 表与结果统计：
   • 按照从左到右的顺序，外层循环从第 1 个元素遍历到最后一个元素（i=1 到 i=n-1），内层循环遍历 i 之前的所有元素（j=0 到 j=i-1），根据状态转移方程更新len[i]和count[i]
   • 遍历结束后，先找到最长递增子序列的长度maxlen，再累加所有len[i] == maxlen的count[i]，得到最长递增子序列的总个数
5. 结果返回：
   • 累加得到的总个数即为最长严格递增子序列的个数，直接返回即可

编写代码：

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();

        vector<int> len(n,1) , count(n,1);

        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                if(nums[i] > nums[j])
                {
                    if(len[i] < len[j] + 1)
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                    else if(len[i] == len[j] + 1)
                    {
                        count[i] += count[j];
                    }
                }
            }
        }

        int maxlen = 0 , maxcount = 0;
        for(int i = 0 ; i < n ; i++)
        {
            if(maxlen < len[i]) 
            {
                maxlen = len[i];
                maxcount = count[i];
            }
            else if(maxlen == len[i])
            {
                maxcount += count[i];
            }
            cout << i << " : " << count[i] << " : " << maxcount << endl;
        }

        return maxcount;
    }
};

四、最长数对链

题目描述：

思路讲解：
本道题需要我们找到最长数对链的长度，问题可拆解为：以每个数对为结尾的最长数对链长度。以下是本道题的具体思路：

1. 预处理：
   • 数对链要求后一个数对的左值大于前一个数对的右值（b < c），为简化判断，先对数组按数对的左值排序，使后续比较更有序
2. 状态表示：
   • dp[i] 表示以第 i 个数对为结尾的最长数对链的长度
3. 状态转移方程：
   • 若 pairs[j][1] < pairs[i][0]（前一个数对的右值小于当前数对的左值，满足跟随关系），则 dp[i] = max(dp[i], dp[j] + 1)
4. 初始化：
   • 所有 dp[i] 初始化为 1：每个数对自身可构成长度为 1 的数对链
5. 填写 DP 表与结果保存：
   • 按照从左到右的顺序，外层循环从第 1 个数对遍历到最后一个（i=1 到 i=n-1），内层循环遍历 i 之前的所有数对（j=0 到 j=i-1），根据状态转移方程更新dp[i]
   • 维护变量 ret，实时记录遍历过程中出现的最大dp值（即最长数对链的长度）
6. 结果返回：
   • 遍历结束后，ret 中存储的就是最长数对链的长度，直接返回即可

编写代码：

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(),pairs.end());
        vector<int> dp(n,1);

        int ret = dp[0];
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                if(pairs[j][1] < pairs[i][0])
                {
                    dp[i] = max(dp[i],dp[j] + 1);
                }
            }
            ret = max(ret,dp[i]);
        }

        return ret;
    }
};

五、最长定差子序列

题目描述：

思路讲解：
本道题需要我们找到数组中相邻元素差等于difference的最长子序列，子序列要求元素顺序不变，但可删除元素，问题可拆解为：以当前元素为结尾的最长定差子序列长度，取决于之前是否存在值为当前元素 - difference的元素，以及该元素对应的最长子序列长度。以下是具体思路：

1. 状态表示：用哈希表hash存储键值对 {arr[i]: dp[i]}，其中arr[i]是数组中的元素，dp[i]表示以arr[i]为结尾的最长定差子序列的长度
2. 状态转移方程：
   • 若哈希表中存在键arr[i] - difference，则以arr[i]为结尾的最长子序列长度为 hash[arr[i] - difference] + 1（在前者基础上延长 1）
   • 若不存在，则以arr[i]为结尾的最长子序列长度为 1（自身单独构成子序列）
   • 用公式表示为：hash[arr[i]] = hash[arr[i] - difference] + 1（若arr[i] - difference不存在，哈希表默认返回 0，结果仍为 1）
3. 初始化：
   • 哈希表初始存入第一个元素：hash[arr[0]] = 1，表示以arr[0]为结尾的子序列长度为 1
   • 结果变量ret初始化为 1，记录当前最长子序列长度
4. 填写 DP 表与结果保存：
   • 按照从左到右的顺序，从数组第 1 个元素遍历到最后一个（i=1到i=n-1），对于每个arr[i]，根据状态转移方程计算其对应的最长子序列长度，并更新到哈希表中
   • 维护变量 ret，实时更新ret为当前哈希表中记录的最大值（即最长定差子序列的长度）
5. 结果返回：
   • 遍历结束后，ret中存储的就是最长定差子序列的长度，直接返回即可

编写代码：

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        unordered_map<int,int> hash;
        hash[arr[0]] = 1;

        int ret = 1;

        for(int i = 1 ; i < n ; i++)
        {
            hash[arr[i]] = hash[arr[i]-difference] + 1;
            ret = max(ret,hash[arr[i]]);
        }

        return ret;
    }
};

六、最长的斐波那契子序列的长度

题目描述：

思路讲解：
本道题需要我们计算最长的斐波那契子序列的长度，斐波那契子序列要求满足： $x_i+x_{i+1}=x_{i+2}$（长度>=3）。在斐波那契数列中，我们需要两个数字就可以确认前一个和后一个元素，一维状态数组无法只能找到一个元素，无法进行向前向后推导，所以本道题需要通过二维状态数组记录以两个元素为结尾的斐波那契子序列长度。以下是具体思路：

1. 状态表示：dp[i][j] 表示以第 i 个元素和第 j 个元素（i < j）为结尾的最长斐波那契子序列的长度
2. 状态转移方程：
   • 对于任意 i < j，设 arr[i] = b，arr[j] = c，则下一个斐波那契元素应为 a = c - b
   • 若 a 存在于数组中且位置 k < i（即 a 在 b 之前），则 dp[i][j] = dp[k][i] + 1（在以 k 和 i 结尾的子序列后添加 j，长度加 1）
   • 若 a 不存在或 k >= i，则 dp[i][j] 保持初始值 2（仅含 i 和 j 两个元素，未形成有效斐波那契子序列）
3. 初始化：
   • 二维数组 dp 所有元素初始化为 2：任意两个元素可作为斐波那契子序列的前两个元素，基础长度为 2
   • 哈希表 hash 存储元素值与索引的映射，用于快速查询 a = arr[j] - arr[i] 是否存在及位置
4. 填写 DP 表与结果保存：
   • 按照从上到下的顺序，外层循环遍历结尾元素 j（0 ≤ j < n），内层循环遍历 j 之前的元素 i（0 ≤ i < j）：
     • 先将 arr[j] 存入哈希表，建立值到索引的映射
     • 对每个 i < j，计算 a = arr[j] - arr[i]，通过哈希表检查 a 是否存在及位置 k
     • 若 k < i，则更新 dp[i][j] = dp[k][i] + 1；否则保持初始值 2
   • 维护变量 ret，实时记录最大的 dp[i][j]（需>=3 才有效）
5. 结果返回：
   • 遍历结束后，若最大长度 ret >= 3 则返回 ret，否则返回 0（无有效子序列）

编写代码：

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int,int> hash;
        vector<vector<int>> dp(n,vector<int>(n,2));

        int ret = 2;
        for(int j = 0 ; j < n ; j++)
        {
            hash[arr[j]] = j;
            for(int i = 0 ; i < j ; i++)
            {
                int num = arr[j] - arr[i];
                if(hash.count(num))
                {
                    int k = hash[num];
                    if(k < i)
                    {
                        dp[i][j] = dp[k][i] + 1;
                    }
                }
                ret = max(ret,dp[i][j]);
            }
        }

        return ret >= 3 ? ret : 0;
    }
};

七、最长等差数列

题目描述：

思路讲解：
本道题需要我们计算最长等差数列的长度，等差数列要求相邻元素差值恒定（即 c - b = b - a）。对于子序列中后两个元素 b（nums [i]）和 c（nums [j]），可推导出前一个元素应为 a = 2b - c，若 a 存在且在 b 之前，则可构成更长的等差数列，本道题需要通过二维状态数组记录以两个元素为结尾的最长等差数列长度。以下是具体思路：

1. 状态表示：dp[i][j] 表示以第 i 个元素（值为 b）和第 j 个元素（值为 c）为结尾（i < j）的最长等差数列的长度
2. 状态转移方程：
   • 计算前一个可能的元素 a = 2*b - c（由等差数列公差 d = c - b 推导，b - a = d）
   • 若 a 存在于数组中且位置 k < i（即 a 在 b 之前），则 dp[i][j] = dp[k][i] + 1（在以 a 和 b 结尾的等差数列后添加 c，长度加 1）
   • 若 a 不存在或 k >= i（a 在 b 之后），则 dp[i][j] 保持初始值 2（仅 b 和 c 两个元素，作为等差数列前两项）
3. 初始化：
   • 二维数组 dp 所有元素初始化为 2：任意两个元素均可作为等差数列的前两项，基础长度为 2
   • 哈希表 hash 用于存储元素值与索引的映射，仅记录 i 之前的元素（确保查询 a 时不包含 i 及之后的元素）
4. 填写 DP 表与结果保存：
   • 按照从上到下的顺序，外层循环遍历中间元素 i（b 的位置），内层循环遍历 i 之后的元素 j（c 的位置）：
     • 对每个 j > i，计算 a = 2*nums[i] - nums[j]，通过哈希表检查 a 是否存在及位置 k
     • 若 k < i（a 在 b 之前），则更新 dp[i][j] = dp[k][i] + 1；否则保持初始值 2
     • 内层循环结束后，将 nums[i]（b）存入哈希表，供后续 i’ > i 时查询
   • 维护变量 ret，实时记录最大的 dp[i][j]（即最长等差数列长度）
5. 结果返回：
   • 遍历结束后，ret 中存储的就是最长等差数列的长度，直接返回即可（至少为 2，因任意两个元素均可构成基础等差数列）

编写代码：

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int,int> hash;
        vector<vector<int>> dp(n,vector<int>(n,2));

        int ret = 2;
        for(int i = 0 ; i < n ; i++)
        {
            for(int j = i + 1 ; j < n ; j++)
            {
                int num = 2*nums[i] - nums[j];
                if(hash.count(num))
                {
                    int k = hash[num];
                    if(k < i)
                    {
                        dp[i][j] = max(dp[i][j] , dp[k][i] + 1);
                    }
                }
                ret = max(ret,dp[i][j]);
            }
            hash[nums[i]] = i;
        }

        return ret;
    }
};

八、等差数列划分 II - 子序列

题目描述：

思路讲解：

本道题需要我们统计所有长度>=3 的等差子序列，等差子序列要求至少 3 个元素，且相邻元素差值恒定，对于任意两个元素，若存在前置元素形成等差关系，可构成新的等差子序列。本道题需要通过二维状态数组记录以两个元素为结尾的等差数列的个数。以下是具体思路：

1. 状态表示：dp[i][j]表示以第 i 个元素和第 j 个元素为结尾的等差子序列的个数
2. 状态转移方程：
   • 计算a = 2*nums[i] - nums[j]，通过哈希表找到所有值为a且索引k < i的位置
   • 每个符合条件的k都对应：以k,i,j为结尾的新子序列（长度 3），以及在dp[k][i]基础上延长的子序列，因此dp[i][j] += dp[k][i] + 1
3. 初始化：
   • dp数组初始化为 0：初始时无任何等差子序列
   • 哈希表hash存储值到索引列表的映射，记录i之前出现的元素位置，用于快速查找a对应的k
4. 填写 DP 表与结果保存：
   • 外层遍历i（中间元素），内层遍历j > i（结尾元素）：
     • 对每个j，计算a并查询哈希表，累加所有符合条件的k对dp[i][j]的贡献
     • 将dp[i][j]累加到结果ret
     • 内层循环结束后，将i加入哈希表
5. 结果返回：ret即为所有等差子序列的总数

编写代码：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        unordered_map<long long,vector<int>> hash;
        vector<vector<int>> dp(n,vector<int>(n,0));

        int ret = 0;
        for(int i = 0 ; i < n ; i++)
        {
            for(int j = i + 1 ; j < n ; j++)
            {
                long long num = 2*(long long)nums[i] - nums[j];
                for(auto& k : hash[num])
                {
                    dp[i][j] += (dp[k][i] + 1);
                }
                ret += dp[i][j];
            }

            hash[nums[i]].push_back(i);
        }

        return ret;
    }
};

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹