动态规划专题：子序列问题的核心模型与优化 | 极客日志

C++算法

动态规划专题：子序列问题的核心模型与优化

综述由AI生成动态规划中的子序列问题关键在于理解“不连续”特性。文章以最长递增子序列（LIS）为基础模型，逐步扩展到摆动序列、定差子序列、斐波那契子序列及等差数列等变体。核心在于状态定义的选取：单点依赖使用一维 DP，双点依赖则需升维至二维 DP。针对特定规律如固定差值，可利用哈希表将复杂度从 O(N²) 降至 O(N)。文中结合 LeetCode 经典例题，提供了完整的 C++ 代码实现与思路解析，帮助掌握线性 DP 的解题套路。

板砖工程师发布于 2026/3/30更新于 2026/4/252 浏览

动态规划专题：子序列问题的核心模型与优化

LIS 模型及其衍生

前言

和子数组（必须连续）不同，子序列可以跳着选。状态定义通常以 dp[i] 表示以 i 位置结尾的最长子序列长度。由于不连续性，i 可以接在 0 到 i-1 任何一个符合条件的 j 后面，因此通常需要双层循环。如果遇到等差、斐波那契等规律，可能需要定两个数，即 dp[i][j] 表示以 i 和 j 结尾。

最长递增子序列

题目描述

找到最长严格递增子序列的长度。

输入：[10,9,2,5,3,7,101,18] 输出：4 ([2,3,7,101])

核心思路

状态：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。
转移：站在 i 位置，往回看所有 j (0 <= j < i)。如果 nums[j] < nums[i]，说明能接在 j 后面。选一个最长的 dp[j] 接上去。 dp[i] = max(dp[j] + 1)。

代码实现

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // 初始化为 1，因为每个元素自己就是一个长度为 1 的子序列
        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++) {
            // 回头看
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ret = (ret, dp[i]);
        }
         ret;
    }
};

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        // 初始化为 1
        vector<int> f(n, 1), g(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    // 此时是上升，接在之前的下降 g[j] 后面
                    f[i] = max(f[i], g[j] + 1);
                } else if (nums[j] > nums[i]) {
                    // 此时是下降，接在之前的上升 f[j] 后面
                    g[i] = max(g[i], f[j] + 1);
                }
            }
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n, 1), count(n, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 > len[i]) {
                        // 发现更长的，重置
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    } else if (len[j] + 1 == len[i]) {
                        // 长度相同，累加方案数
                        count[i] += count[j];
                    }
                }
            }
            maxLen = max(maxLen, len[i]);
        }
        // 统计所有达到 maxLen 的个数
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (len[i] == maxLen) ret += count[i];
        }
        return ret;
    }
};

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        // 关键步骤：排序
        sort(pairs.begin(), pairs.end());
        int n = pairs.size();
        vector<int> dp(n, 1);
        int ret = 1;
        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;
    }
};

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> hash; // val -> length
        int ret = 1;
        for (int x : arr) {
            // 直接查找前一个数是否存在
            hash[x] = hash[x - difference] + 1;
            ret = max(ret, hash[x]);
        }
        return ret;
    }
};

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        // 值 -> 下标 映射
        unordered_map<int, int> idxMap;
        for (int i = 0; i < n; i++) idxMap[arr[i]] = i;
        
        // dp[i][j] 以 i, j 结尾
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 0;
        
        // 先固定 j (最后一个数)
        for (int j = 2; j < n; j++) {
            // 再枚举 i (倒数第二个数)
            for (int i = 1; i < j; i++) {
                int target = arr[j] - arr[i];
                // 如果 target 存在，且在 i 之前
                if (target < arr[i] && idxMap.count(target)) {
                    int k = idxMap[target];
                    dp[i][j] = dp[k][i] + 1;
                    ret = max(ret, dp[i][j]);
                }
            }
        }
        return ret < 3 ? 0 : ret;
    }
};

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        // dp[i][j] 表示以 i 和 j 结尾
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        
        // 为了加速找 k，可以用 map 存
        // 注意：因为有重复元素，我们要在遍历过程中动态更新 hash
        unordered_map<int, int> hash;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int target = 2 * nums[i] - nums[j]; // nums[i] - (nums[j] - nums[i])
                if (hash.count(target)) {
                    int k = hash[target];
                    dp[i][j] = dp[k][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
            // 关键：遍历完 i 之后，才把 i 放入 hash
            // 这样保证取到的 k 一定在 i 之前
            hash[nums[i]] = i;
        }
        return ret;
    }
};

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        long long ans = 0;
        // dp[i][j] 以 i, j 结尾的等差数列个数
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // 优化：值 -> 下标列表
        unordered_map<long long, vector<int>> map;
        for (int i = 0; i < n; i++) map[nums[i]].push_back(i);
        
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                long long target = 2LL * nums[i] - nums[j];
                if (map.count(target)) {
                    for (int k : map[target]) {
                        if (k < i) {
                            // 累加个数
                            dp[i][j] += dp[k][i] + 1;
                        } else {
                            break; // 因为 map 里下标是递增的
                        }
                    }
                }
                ans += dp[i][j];
            }
        }
        return (int)ans;
    }
};