您现在的位置是：首页 >学无止境 >算法总结-动态规划-最大子数组和/最长公共子序列/最长递增子序列网站首页学无止境

算法总结-动态规划-最大子数组和/最长公共子序列/最长递增子序列

烈焰的冰玫瑰 2026-04-04 12:01:05
简介算法总结-动态规划-最大子数组和/最长公共子序列/最长递增子序列

前言

  动态规划的题单可以刷 灵茶山艾府 的题单分享丨【题单】动态规划（入门/背包/状态机/划分/区间/状压/数位/树形/数据结构优化）。本文是该分享的学习笔记。

最大子数组和

最大子数组和
题目描述：
  给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
  子数组 是数组中的一个连续部分。

前缀和

  定义前缀和为：
s [ 0 ] = 0 ; s [ i + 1 ] = ∑ j = 0 i n u m s [ i ] ; s[0] = 0;\ s[i+1] = sum_{j=0}^{i}nums[i]; s[0]=0;s[i+1]=j=0∑i​nums[i];
  这样对于子数组 n u m s [ i : j ] nums[i:j] nums[i:j] 的元素和就可以表示为 s [ j + 1 ] − s [ i ] s[j+1] - s[i] s[j+1]−s[i] 的两个前缀和之差，我们遍历元素 n u m s [ i ] nums[i] nums[i] 的同时维护 i i i 之前前缀和的最小值 m i n P r e s u m minPresum minPresum, 这样以 n u m s [ i ] nums[i] nums[i] 为结尾的最大的子数组和就是 n u m s [ i ] − m i n P r e s u m nums[i] - minPresum nums[i]−minPresum，由于子数组不为空，所以要先更新最大子数组和，再更新 m i n P r e s u m minPresum minPresum。
  由于我们每次更新只用到了前一个元素的前缀和，因此我们可以只用维护一个前缀和的值。

代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int presum = 0;
        int maxsum = INT_MIN;
        int minPresum = 0;
        for(auto &x:nums){
            presum += x;
            maxsum = max(maxsum, presum-minPresum);
            minPresum = min(minPresum, presum);
        }
        return maxsum;
    }
};

动态规划

  定义 d p [ i ] dp[i] dp[i] 表示以 i i i 结尾的最大子数组和，那么答案就是 m a x ( d p [ i ] ) max(dp[i]) max(dp[i])，每次选择可以选择将以前面元素为结尾的最大子数组和加起来构成新的子数组，就是 d p [ i − 1 ] + n u m s [ i ] dp[i-1] + nums[i] dp[i−1]+nums[i]; 或者不加， n u m s [ i ] nums[i] nums[i] 单独为一个子数组， d p [ i ] dp[i] dp[i] 就是取两者的最大值：
d p [ i ] = m a x ( d p [ i − 1 ] + n u m s [ i ] , n u m s [ i ] ) dp[i] = max(dp[i-1]+nums[i], nums[i]) dp[i]=max(dp[i−1]+nums[i],nums[i])
也就是：
d p [ i ] = m a x ( 0 , d p [ i − 1 ] ) + n u m s [ i ] dp[i] = max(0,dp[i-1])+nums[i] dp[i]=max(0,dp[i−1])+nums[i]
为了避免出现负数下标，那么用 d p [ i + 1 ] dp[i+1] dp[i+1] 表示 d p [ i ] dp[i] dp[i]， d p [ 0 ] dp[0] dp[0] 表示没有任何元素的最大子数组和，所以 d p [ 0 ] = 0 dp[0] = 0 dp[0]=0。那么有状态转移方程：
d p [ 0 ] = 0 d p [ i + 1 ] = m a x ( 0 , d p [ i ] ) + n u m s [ i ] dp[0] = 0\ dp[i+1] = max(0, dp[i]) + nums[i] dp[0]=0dp[i+1]=max(0,dp[i])+nums[i]
  由于状态转移只与前一个状态有关，因此可以用只用一个变量来滚动计算。

代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp = 0;
        int maxSum = INT_MIN;
        for(auto &x:nums){
            dp = max(0, dp) + x;
            maxSum = max(maxSum, dp);
        }
        return maxSum;
    }
};

最长公共子序列

最长公共子序列
题目描述：
  给定两个字符串 s 和 t，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
  一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
  例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
  两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路：
  如果我们定义 d f s ( i , j ) dfs(i, j) dfs(i,j) 来表示以求解 s [ 0 : i ] s[0:i] s[0:i] 和 t [ 0 : j ] t[0:j] t[0:j] 的最长公共子序列，我们看是否能将其转化为求解其子问题得来。
  当 s [ i ] = = t [ j ] s[i] == t[j] s[i]==t[j] 时，说明 s [ i ] s[i] s[i] 是 s s s 和 t t t 的一个公共字符，它能够作为 s s s 和 t t t 和公共子序列的一部分，那么最终的公共子序列为 d f s ( i − 1 , j − 1 ) dfs(i-1, j-1) dfs(i−1,j−1) 加上 s [ i ] s[i] s[i]。
  那么有没有可能 s [ i ] s[i] s[i] 和 t [ 0 : j − 1 ] t[0:j-1] t[0:j−1] 中的字符匹配而不是和 t [ j ] t[j] t[j] 匹配能够获得更优的解呢？假设 s [ i ] s[i] s[i] 不和 t [ j ] t[j] t[j] 匹配，而和 t [ k ] t[k] t[k] 匹配，其中 k < j k<j k<j，那么得到的最长公共子序列为 d f s ( i − 1 , k − 1 ) dfs(i-1,k-1) dfs(i−1,k−1) + s[i]，而 t [ 0 : k − 1 ] t[0:k-1] t[0:k−1] 是 t [ 0 : j − 1 ] t[0:j-1] t[0:j−1] 的子序列，因此匹配出的最长公共子序列是 t [ 0 : k − 1 ] t[0:k-1] t[0:k−1] 的子序列，一定也是 t [ 0 : j − 1 ] t[0:j-1] t[0:j−1] 的子序列，而 t [ 0 : j − 1 ] t[0:j-1] t[0:j−1]还有更多的字符共可能的匹配，所以 d f s ( i − 1 , k − 1 ) ≤ d f s ( i − 1 , j − 1 ) dfs(i-1, k-1) leq dfs(i-1, j-1) dfs(i−1,k−1)≤dfs(i−1,j−1)成立。同理， t [ j ] t[j] t[j] 也不能和 s [ 0 : i − 1 ] s[0:i-1] s[0:i−1] 中的字符匹配以获得更优的解。
  当 s [ i ] ! = t [ j ] s[i]!=t[j] s[i]!=t[j]，此时不能确定 s [ i ] s[i] s[i] 或 t [ j ] t[j] t[j] 谁可以做最长公共子序列中的字符。那么考虑用 s [ i ] s[i] s[i] 和 t [ 0 : j − 1 ] t[0:j-1] t[0:j−1]中的字符匹配： d f s ( i , j − 1 ) dfs(i, j-1) dfs(i,j−1)；或者 t [ j ] t[j] t[j] 和 s [ 0 : i − 1 ] s[0:i-1] s[0:i−1] 中的字符匹配： d f s ( i − 1 , j ) dfs(i-1, j) dfs(i−1,j)。
  那么需要考虑 s [ i ] s[i] s[i] 和 t [ j ] t[j] t[j] 都不能被匹配的情况吗？事实上这种情况 d f s ( i − 1 , j − 1 ) dfs(i-1,j-1) dfs(i−1,j−1) 包含在 d f s ( i − 1 , j ) dfs(i-1, j) dfs(i−1,j) 和 d f s ( i ， j − 1 ) dfs(i，j-1) dfs(i，j−1) 之中了。当 d f s ( i − 1 , j ) dfs(i-1,j) dfs(i−1,j) 中不选 t [ j ] t[j] t[j], 或者当 d f s ( i , j − 1 ) dfs(i, j-1) dfs(i,j−1) 中不选 s [ i ] s[i] s[i] 的时候就会变为 d f s ( i − 1 , j − 1 ) dfs(i-1, j-1) dfs(i−1,j−1)，因此不需要额外考虑。
  这道题用 d f s ( i , j ) dfs(i,j) dfs(i,j) 表示最长公共子序列的长度，这样就得到了递归方程：
d f s ( i , j ) = { d f s ( i − 1 , j − 1 ) + 1 , s [ i ] = t [ j ] m a x ( d f s ( i − 1 , j ) , d f s ( i , j − 1 ) ) , s [ i ] ≠ t [ j ] dfs(i,j)=egin{cases} dfs(i-1,j-1) +1, &quad quad s[i]=t[j]\ max(dfs(i-1,j), dfs(i,j-1)), &quad quad s[i] eq t[j] end{cases} dfs(i,j)={dfs(i−1,j−1)+1,max(dfs(i−1,j),dfs(i,j−1)),​s[i]=t[j]s[i]=t[j]​

记忆化搜索

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1 = text1.size(), n2 = text2.size();
        vector dp(n1, vector<int>(n2, -1));
        auto dfs = [&](this auto&& dfs, int i, int j)->int{
            if(i<0 || j<0) return 0;
            if(dp[i][j]!=-1) return dp[i][j];
            if(text1[i]==text2[j]) return dp[i][j] = dfs(i-1,j-1)+1;
            else{
                return dp[i][j] = max(dfs(i,j-1), dfs(i-1, j));
            }
        };
        return dfs(n1-1, n2-1);   
    }
};

动态规划

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1 = text1.size(), n2 = text2.size();
        vector dp(n1+1, vector<int>(n2+1));
        for(int i=0;i<n1;++i){
            for(int j=0;j<n2;++j){
                if(text1[i]==text2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }
                else{
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
                }
            }
        }
        return dp[n1][n2];
    }
};

转化为两个数组的空间优化

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1 = text1.size(), n2 = text2.size();
        vector dp(2, vector<int>(n2+1));
        for(int i=0;i<n1;++i){
            for(int j=0;j<n2;++j){
                if(text1[i]==text2[j]){
                    dp[(i+1)%2][(j+1)] = dp[i%2][j] + 1;
                }
                else{
                    dp[(i+1)%2][j+1] = max(dp[i%2][j+1], dp[(i+1)%2][j]);
                }
            }
        }
        return dp[n1%2][n2];
    }
};

一个数组

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1 = text1.size(), n2 = text2.size();
        vector<int> dp(n2+1);
        for(int i=0;i<n1;++i){
            int pre = 0;
            for(int j=0;j<n2;++j){
                int tmp = dp[j+1];
                dp[j+1] = text1[i]==text2[j]?pre+1:max(dp[j], dp[j+1]);
                pre = tmp;
            }
        }
        return dp[n2];
    }
};

最长递增子序列

最长递增子序列
题目描述：
  给你一个整数数组 n u m s nums nums ，找到其中最长严格递增子序列的长度。
  子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列。

动态规划

  定义 d p [ i ] dp[i] dp[i] 表示以 n u m s [ i ] nums[i] nums[i] 结尾的最长递增子序列的长度。那么它的上一个元素就要比它小，找到所有 n u m s [ i ] nums[i] nums[i] 之前的比 n u m s [ i ] nums[i] nums[i] 小的元素，取以它们为结尾的最长递增子序列和 n u m s [ i ] nums[i] nums[i] 相接，其中最大的一个长度就是以 n u m s [ i ] nums[i] nums[i] 结尾的最长递增子序列的长度。最后答案取所有 d p [ i ] dp[i] dp[i] 的最大值。

代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for(int i=1;i<n;++i){
            for(int j=i-1;j>=0;--j){
                if(nums[i]>nums[j]){
                   dp[i] = max(dp[j]+1, dp[i]); 
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

贪心+二分：（处理的情况有限）

  定义 g [ i ] g[i] g[i] 表示长度为 i i i 的递增子序列的末尾元素的最小值，每次遍历 n u m s [ i ] nums[i] nums[i] 时更新 g g g 中第一个大于等于 n u m s [ i ] nums[i] nums[i] 的值为 n u m s [ i ] nums[i] nums[i], 如果不存在，则将 n u m s [ i ] nums[i] nums[i] 加入到数组 g g g 的末尾。

代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> g;
        for(auto &x:nums){
            auto it = lower_bound(g.begin(), g.end(), x);
            if(it==g.end()) g.emplace_back(x);
            else{
                g[it-g.begin()] = x;
            }
        }
        return g.size();
    }
};

线段树（基于值域处理）

  由于动态规划的第二重循环是在找已经遍历的元素中在 [ m i n V , n u m s [ i ] − 1 ] [minV, nums[i]-1] [minV,nums[i]−1] 这个值域中的元素结尾的子序列的最长长度，因此可以考虑用线段树来优化查询。定义 Node 节点，表示以 [ l e f t , r i g h t ] [left,right] [left,right] 为值域的元素结尾的所有递增子序列的最长长度，更新时就将当前 nums[i] 所表示的区间 [ n u m s [ i ] , n u m s [ i ] ] [nums[i], nums[i]] [nums[i],nums[i]] 更新，同时更新所有包含该区间的区间，最后以 [ m i n V , m a x V ] [minV, maxV] [minV,maxV] 为值域结尾的最长递增子序列的长度就是下标为 1 的节点值。

struct Node{
    int left=0, right=0, val=0;
    Node(){}
    Node(int left, int right):left(left), right(right){}
};

class SegmentTree{
private:
    vector<int> nums;
    vector<Node> tree;
    int k;
    void build(int u, int left, int right){
        tree[u] = Node(left, right);
        if(left==right) return;
        else{
            int mid = left + (right-left)/2;
            build(2*u, left, mid);
            build(2*u+1, mid+1, right);
        }
    }

    void pushup(int u){
        tree[u].val = max(tree[2*u].val, tree[2*u+1].val);
        if(u>1) pushup(u/2);
    }

public:
    SegmentTree(vector<int>& nums, int k, int maxV):nums(nums.size()),k(k){
        tree.resize(4*maxV);
        build(1, 1, maxV);
        for(int i=0;i<nums.size();++i){
            update(1, nums[i]);
        }
    }

    void update(int u, int val){
        if(tree[u].left == val && tree[u].right == val){
            int preLen = range(1, max(1, val-k), val-1)+1;
            tree[u].val = preLen;
            pushup(u/2);
        }
        else{
            int mid = tree[u].left + (tree[u].right-tree[u].left)/2;
            if(val>mid){
                update(2*u+1, val);
            }
            else{
                update(2*u, val);
            }
        }
    }

    int range(int u, int left, int right){
        if(right<left) return 0;
        if(left==tree[u].left && right==tree[u].right) return tree[u].val;
        else{
            int mid = tree[u].left + (tree[u].right-tree[u].left)/2;
            if(left>mid) return range(2*u+1, left, right);
            else if(right<=mid) return range(2*u, left, right);
            else{
                return max(range(2*u, left, mid), range(2*u+1, mid+1, right));
            }
        }
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int minV = abs(*min_element(nums.begin(), nums.end()))+1;
        for(auto &num:nums) num += minV;
        int maxV = *max_element(nums.begin(), nums.end());
        SegmentTree segmentTree(nums, 1e6, maxV);
        return segmentTree.range(1, 1, maxV);
    }
};

  可以简化一下写法。参考自：灵茶山艾府.线段树优化 DP（Python/Java/C++/Go）

class Solution {
    vector<int> max;

    void modify(int o, int l, int r, int i, int val) {
        if (l == r) {
            max[o] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) modify(o * 2, l, m, i, val);
        else modify(o * 2 + 1, m + 1, r, i, val);
        max[o] = std::max(max[o * 2], max[o * 2 + 1]);
    }

    // 返回区间 [L,R] 内的最大值
    int query(int o, int l, int r, int L, int R) { // L 和 R 在整个递归过程中均不变，将其大写，视作常量
        if (L <= l && r <= R) return max[o];
        int res = 0;
        int m = (l + r) / 2;
        if (L <= m) res = query(o * 2, l, m, L, R);
        if (R > m) res = std::max(res, query(o * 2 + 1, m + 1, r, L, R));
        return res;
    }

public:
    int lengthOfLIS(vector<int> &nums) {
        int minV = abs(*min_element(nums.begin(), nums.end()))+1;
        for(auto &num:nums) num += minV;
        int u = *max_element(nums.begin(), nums.end());
        max.resize(u * 4);
        for (int x: nums) {
            if (x == 1) modify(1, 1, u, 1, 1);
            else {
                int res = 1 + query(1, 1, u, 1, x - 1);
                modify(1, 1, u, x, res);
            }
        }
        return max[1];
    }
};

例题

最大子数组和

918. 环形子数组的最大和

题目描述：
  给定一个长度为 n n n 的环形整数数组 n u m s nums nums ，返回 n u m s nums nums 的非空 子数组 的最大可能和 。
  环形数组 意味着数组的末端将会与开头相连呈环状。形式上， n u m s [ i ] nums[i] nums[i] 的下一个元素是 n u m s [ ( i + 1 ) % n ] nums[(i + 1) \%n] nums[(i+1)%n] ， n u m s [ i ] nums[i] nums[i] 的前一个元素是 n u m s [ ( i − 1 + n ) % n ] nums[(i - 1 + n)\%n] nums[(i−1+n)%n] 。
  子数组 最多只能包含固定缓冲区 n u m s nums nums 中的每个元素一次。形式上，对于子数组 n u m s [ i ] nums[i] nums[i], n u m s [ i + 1 ] nums[i + 1] nums[i+1], …, n u m s [ j ] nums[j] nums[j] ，不存在 i < = k 1 , k 2 < = j i <= k1, k2 <= j i<=k1,k2<=j 其中 k 1 % n = = k 2 % n k1 \% n == k2 \% n k1%n==k2%n 。

思路：
  环形子数组有两种情况，一种是连续的子数组，一种是由头部连续子数组和尾部连续子数组拼接得来的子树组。前者的最大和可以用求解最大子数组和的思路求解，后者如果正面求解，需要考虑当头部取 n u m s [ i ] nums[i] nums[i] 为结尾时，以 n u m s [ n − 1 ] nums[n-1] nums[n−1] 为结尾，以 n u m s [ i − 1 ] nums[i-1] nums[i−1] 为开头的子数组的最大子数组和，这样考虑起来较为麻烦，因此 正难则反，考虑反向思考，第二种情况的最大和就等价于数组的和减去中间不选的那个连续子数组的最小和，这样，我们就能够较为容易地求解了，需要注意的是，由于子数组最小有一个元素，因此遍历最小和的时候要从 1 开始，到 n-2。

代码：

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        int ans = nums[0], rs = 0;
        int sum = 0;
        for(int i=0;i<n;++i){
            sum += nums[i];
            rs = max(0, rs) + nums[i];
            ans = max(ans, rs);
        }

        int ans1 = 0, rs1 = 0;
        for(int i=1;i<n-1;i++){            
            rs1 = min(0, rs1) + nums[i];
            ans1 = min(ans1, rs1);
        }
        return max(ans, sum-ans1);
    }
};

2321. 拼接数组的最大分数

题目描述：
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。

你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，接着 交换 两个子数组 nums1[left...right] 和 nums2[left...right] 。

例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15] ，整数选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15] 。
你可以选择执行上述操作 一次 或不执行任何操作。

数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。

返回 可能的最大分数 。

子数组 是数组中连续的一个元素序列。arr[left...right] 表示子数组包含 nums 中下标 left 和 right 之间的元素（含 下标 left 和 right 对应元素）。

思路：
  考虑两个数组之间的差值构成的数组，nums1 和 nums2 交换一个子数组和得到的和就是 nums1 元素之和加上这个交换的子数组对应的差值子数组之和，要使 nums1 最大，就是让这个差值数组的子数组和最大，反之，nums2 也是类似。

代码：

class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int maxN = 0, minN = INT_MAX;
        int ts = 0, us = 0;
        int sum1 = 0, sum2 = 0;
        for(int i=0;i<n;++i){
            sum1 += nums1[i];
            sum2 += nums2[i];
            int diff = nums2[i] - nums1[i];
            ts = max(0,ts) + diff;
            us = min(0,us) + diff;
            maxN = max(maxN, ts);
            minN = min(minN, us);
        }
        return max(sum1 + maxN, sum2-minN);
    }
};

  也可以将计算 num1 交换后的最大和封装成一个函数，计算 nums2 交换后的最大值只需要把 nums1 和 nums2 交换参数位置即可。

class Solution {
    int solve(vector<int>& nums1, vector<int>& nums2) {
        int s1 = 0, max_sum = 0, f = 0;
        for (int i = 0; i < nums1.size(); i++) {
            s1 += nums1[i];
            f = max(f, 0) + nums2[i] - nums1[i];
            max_sum = max(max_sum, f);
        }
        return s1 + max_sum;
    }

public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        return max(solve(nums1, nums2), solve(nums2, nums1));
    }
};

最长公共子序列

72. 编辑距离

题目描述：

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • ;替换一个字符

思路：
  定义 d f s ( i , j ) dfs(i, j) dfs(i,j) 为求解 w o r d 1 [ 0 : i ] word1[0:i] word1[0:i] 转化为 w o r d 2 [ 0 : j ] word2[0:j] word2[0:j] 的最少操作数，那么就有这样几种情况：

  • 当 w o r d 1 [ i ] = = w o r d 2 [ j ] word1[i]==word2[j] word1[i]==word2[j]，此时不用进行任何操作， w o r d 1 word1 word1 拥有的字符少 1， w o r d 2 word2 word2 需要匹配的字符也少 1。 d f s ( i , j ) = d f s ( i − 1 , j − 1 ) dfs(i, j) = dfs(i-1, j-1) dfs(i,j)=dfs(i−1,j−1)
  • 当 w o r d 1 [ i ] ! = w o r d 2 [ j ] word1[i]!=word2[j] word1[i]!=word2[j]，此时有三种操作可供选择，取三种操作的最小值：
    • 插入一个字符，那么 w o r d 1 word1 word1 拥有的字符不变， w o r d 2 word2 word2 需要匹配的字符少 1，操作数加一。 d f s ( i , j ) = d f s ( i , j − 1 ) + 1 dfs(i, j) = dfs(i, j-1)+1 dfs(i,j)=dfs(i,j−1)+1
    • 删除一个字符，那么 w o r d 1 word1 word1 拥有的字符少 1， w o r d 2 word2 word2 需要匹配的字符不变，操作数加一。 d f s ( i , j ) = d f s ( i , j ) + 1 dfs(i, j) = dfs(i, j)+1 dfs(i,j)=dfs(i,j)+1
    • 替换一个字符， w o r d 1 word1 word1 拥有的字符少 1， w o r d 2 word2 word2 需要匹配的字符也少 1，操作数加一。 d f s ( i , j ) = d f s ( i − 1 , j − 1 ) + 1 dfs(i, j) = dfs(i-1, j-1)+1 dfs(i,j)=dfs(i−1,j−1)+1
        所以递归方程就是：
      d f s ( i , j ) = { d f s ( i − 1 , j − 1 ) , w o r d 1 [ i ] = w o r d 2 [ j ] m i n ( d f s ( i , j − 1 ) , d f s ( i − 1 , j ) , d f s ( i , j ) ) + 1 , w o r d 1 [ i ] ≠ w o r d 2 [ j ] dfs(i,j)=egin{cases} dfs(i-1,j-1) , &quad quad word1[i]=word2[j]\ min(dfs(i,j-1), dfs(i-1,j), dfs(i,j))+1, &quad quad word1[i] eq word2[j] end{cases} dfs(i,j)={dfs(i−1,j−1),min(dfs(i,j−1),dfs(i−1,j),dfs(i,j))+1,​word1[i]=word2[j]word1[i]=word2[j]​

  边界条件：当 j < 0 j<0 j<0 时，此时需要将长度为 i + 1 i+1 i+1 的字符串变为空字符串，需要全部删除，操作数是 i + 1 i+1 i+1；当 i < 0 i<0 i<0 时，此时需要将空字符串变为长度为 j + 1 j+1 j+1 的字符串，需要插入 j + 1 j+1 j+1 个字符，操作数是 j + 1 j+1 j+1。

记忆化搜索代码：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector dp(m, vector<int>(n, -1));
        auto dfs = [&](this auto &&dfs, int i, int j)->int{
            if(j<0) return i+1;
            if(i<0) return j+1;
            if(dp[i][j]!=-1) return dp[i][j];
            if(word1[i]==word2[j]){
                return dp[i][j] = dfs(i-1, j-1);
            }
            else{
                return dp[i][j] = min({dfs(i-1, j) + 1, dfs(i-1, j-1)+1, dfs(i, j-1)+1});
            }
        };
        return dfs(m-1, n-1);
        //O(mn) 时间复杂度
        //O(mn) 空间复杂度
    }
};

转化为动态规划代码：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector dp(m+1, vector<int>(n+1));
        for(int i=0;i<m;++i){
            dp[i+1][0] = i+1;
        }
        for(int j=0;j<n;++j){
            dp[0][j+1] = j+1;
        }
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(word1[i]==word2[j]){
                    dp[i+1][j+1] = dp[i][j];
                }
                else{
                    dp[i+1][j+1] = min({dp[i][j+1], dp[i][j], dp[i+1][j]})+1;
                }
            }
        }
        return dp[m][n];
    }
};

空间优化：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<int> dp(n+1);
        iota(dp.begin(), dp.end(), 0);
        for(auto &x:word1){
            int tmp = dp[0];
            dp[0]++;   //dp[0]没有在下面的循环中遍历，但是有改变
            for(int j=0;j<n;++j){
                int t = dp[j+1];
                dp[j+1] = x==word2[j]?tmp:min({dp[j+1], tmp, dp[j]})+1;
                tmp = t;
            }
        }
        return dp[n];
    }
};

1639.通过给定词典构造目标字符串的方案数

题目描述：

给你一个字符串列表 words 和一个目标字符串 target 。words 中所有字符串都 长度相同 。

你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：

  • 从左到右依次构造 target 的每一个字符。
  • 为了得到 t a r g e t target target 第 i 个字符（下标从 0 开始），当 target[i] = words[j][k] 时，你可以使用 words 列表中第 j 个字符串的第 k 个字符。
  • 一旦你使用了 words 中第 j 个字符串的第 k 个字符，你不能再使用 words 字符串列表中任意单词的第 x 个字符（x <= k）。也就是说，所有单词下标小于等于k 的字符都不能再被使用。
  • 请你重复此过程直到得到目标字符串 target 。

请注意， 在构造目标字符串的过程中，你可以按照上述规定使用 words 列表中 同一个字符串 的 多个字符 。

请你返回使用 words 构造 target 的方案数。由于答案可能会很大，请对 1 0 9 + 7 10^9 + 7 109+7 取余 后返回。

思路：
  首先要理解题目的意思，题目的意思是叫我们每次构造时可以选择 words 中所有字符串下标为 i 的字符进行构造，如果选择了，就不能选择之前的，那么我们可以把所有当前下标为 i 时可以选择的字符统计起来，记为word[i]，那么每次就从word[i]中的字符选择，选择后就不能选择 word[i] 之前的字符进行构造，这和构造公共子序列是一样的。
  定义 d f s ( i , j ) dfs(i,j) dfs(i,j) 表示从 word[i] 之前的字符中进行选择，构造 target[0:j] 的方案数。
  那么每次选择存在的情况：

  • target[j] 在 word[i] 中，此时可以选择用 word[i] 中的字符构造，也可以选择跳过，用之前的字符构造。
    • 如果选择，那么方案数为字符的个数乘以用 word[i-1] 之前的字符构造 target[0:j-1] 的方案数： d f s ( i , j ) = d f s ( i − 1 , j − 1 ) ∗ w o r d [ i ] [ t a r g e t [ j ] ] dfs(i,j)=dfs(i-1,j-1)*word[i][target[j]] dfs(i,j)=dfs(i−1,j−1)∗word[i][target[j]]
    • 如果不选择，那么只能用 word[i-1] 之前的字符构造 target[0:j-1] ： d f s ( i , j ) = d f s ( i − 1 , j − 1 ) dfs(i, j) = dfs(i-1,j-1) dfs(i,j)=dfs(i−1,j−1)
  • target[j] 不在 word[i] 中，那么也只能用 word[i-1] 之前的字符构造 target[0:j-1] ： d f s ( i , j ) = d f s ( i − 1 , j − 1 ) dfs(i, j) = dfs(i-1,j-1) dfs(i,j)=dfs(i−1,j−1)

  所以最后的状态转移方程为：
d f s ( i , j ) = { d f s ( i − 1 , j − 1 ) ∗ w o r d [ i ] [ t a r g e t [ j ] ] + d f s ( i − 1 , j ) , t a r g e t [ j ]   i n   w o r d [ i ] d f s ( i − 1 , j ) , t a r g e t [ j ]   n o t   i n   w o r d [ i ] dfs(i,j) = egin{cases} dfs(i-1,j-1)*word[i][target[j]] + dfs(i-1,j), &quad target[j] in word[i] \ dfs(i-1,j),&quad target[j] not in word[i] end{cases} dfs(i,j)={dfs(i−1,j−1)∗word[i][target[j]]+dfs(i−1,j),dfs(i−1,j),​target[j] in word[i]target[j] not in word[i]​

  边界条件：当 j<0 时，此时不需要选择任何的字符来构造空字符串，所以方案数为 1， 当 i<0 && j>=0 时没有字符来构造长度为 j+1 的字符串，因此方案数为 0。

记忆化搜索代码：

class Solution {
private:
    static const int MOD = 1e9 + 7;
public:
    int numWays(vector<string>& words, string target) {
        int len = words.size(), n = words[0].size(), m = target.size();
        if(n<m) return 0;
        vector<unordered_map<char, long long>> word(n);
        for(int i=0;i<n;++i){
            for(int j=0;j<len;++j){
                word[i][words[j][i]]++;
            }
        }
        vector dp(n, vector<int>(m, -1));
        auto dfs = [&](this auto&& dfs, int i, int j)->long long{
            if(j<0) return 1;
            if(i<0) return 0;
            if(dp[i][j]!=-1) return dp[i][j];
            if(word[i].count(target[j])){
                return dp[i][j] = ((word[i][target[j]]*dfs(i-1,j-1))%MOD + dfs(i-1, j)%MOD)%MOD;
            }
            else{
                return dp[i][j] = dfs(i-1, j);
            }
        };
        return dfs(n-1, m-1);
    }
};

动态规划代码：

class Solution {
private:
    static const int MOD = 1e9 + 7;
public:
    int numWays(vector<string>& words, string target) {
        int len = words.size(), n = words[0].size(), m = target.size();
        if(n<m) return 0;
        vector<unordered_map<char, int>> word(n);
        for(int i=0;i<n;++i){
            for(int j=0;j<len;++j){
                word[i][words[j][i]]++;
            }
        }
        vector dp(n+1, vector<long long>(m+1));
        for(int j=0;j<m;++j){
            dp[0][j] = 0;
        }
        for(int i=0;i<n;++i){
            dp[i][0] = 1;
        }
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(word[i].count(target[j])){
                    dp[i+1][j+1] = ((word[i][target[j]]*dp[i][j])%MOD + dp[i][j+1]%MOD)%MOD;
                }
                else{
                    dp[i+1][j+1] = dp[i][j+1];
                }
            }
        }
        return dp[n][m];
    }
};

空间优化，代码优化

class Solution {
private:
    static const int MOD = 1e9 + 7;
public:
    int numWays(vector<string>& words, string target) {
        int len = words.size(), n = words[0].size(), m = target.size();
        if(n<m) return 0;
        int word[n][26];
        memset(word, 0, sizeof(word));
        for(int i=0;i<n;++i){
            for(int j=0;j<len;++j){
                word[i][words[j][i]-'a']++;
            }
        }
        long long dp[m];
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<n;++i){
            long long tmp = 1;
            for(int j=0;j<m;++j){
                int t = dp[j];
                if(word[i][target[j]-'a']!=0){
                    dp[j] = ((word[i][target[j]-'a']*tmp)%MOD + dp[j]%MOD)%MOD;
                }
                tmp = t;
            }
        }
        return dp[m-1];
    }
};

最长递增子序列

673. 最长递增子序列的个数

题目描述：

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

思路：
  需要在维护以 nums[i] 结尾的最长递增子序列的长度时，同时维护一个该最长递增子序列的种类数，由于数据量比较小，可以直接使用二重循环的动态规划。

代码：

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int,int>> dp(n, make_pair(1,1));
        for(int i=0;i<n;++i){
            for(int j=i-1;j>=0;--j){
                if(nums[j]<nums[i]){
                    int newLen = dp[j].first + 1;
                    if(newLen == dp[i].first){
                        dp[i].second += dp[j].second;
                    }
                    else if(newLen>dp[i].first){
                        dp[i].first = newLen;
                        dp[i].second = dp[j].second;
                    }
                }
            }
        }
        int ansLen = 0, ansN = 0;
        for(int i=0;i<n;++i){
            if(ansLen<dp[i].first){
                ansLen = dp[i].first;
                ansN = dp[i].second;
            }
            else if(ansLen==dp[i].first){
                ansN += dp[i].second;
            }
        }        
        return ansN;
    }
};

1964. 找出到每个位置为止最长的有效障碍赛跑路线

题目描述：

你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。

对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：

  • 你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
  • 在这条路线中，必须包含第 i 个障碍。
  • 你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
  • 除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高

返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

class Solution {
public:
        int kIncreasing(vector<int>& arr, int k) {
        int res = 0;
        for(int i = 0;i < k; i++){
            vector<int> g;
            int cnt = 0;
            for(int j =  i;j < arr.size();j += k){
                int x = arr[j];
                auto it = ranges::upper_bound(g,x);
                if(it == g.end()) g.push_back(x);
                else *it = x;
                cnt++;
            }
            res += cnt - g.size(); 
        }
        return res;
    }
};

思路：
  理解题目的意思，发现题目要求我们求的其实是数组的最长非递减子序列，由于 n 最大可以取到 1 0 5 10^5 105，因此使用动态规划来做这道题目会导致超时，所以可以考虑使用 贪心 + 二分的做法来求解这道题目。

代码：

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        int n = obstacles.size();
        vector<int> g = {obstacles[0]};
        vector<int> ans(n);
        ans[0] = 1;
        for(int i=1;i<n;++i){
            if(g.back()<=obstacles[i]){
                g.emplace_back(obstacles[i]);
                ans[i] = g.size();
            }
            else{
                int index = upper_bound(g.begin(), g.end(), obstacles[i]) - g.begin();
                ans[i] = index+1;
                g[index] = obstacles[i];
            }
        }
        return ans;
    }
};

2407. 最长递增子序列 II

题目描述：
给你一个整数数组 nums 和一个整数 k 。

找到 nums 中满足以下要求的最长子序列：

  • 子序列 严格递增
  • 子序列中相邻元素的差值 不超过 k 。

请你返回满足上述要求的 最长子序列 的长度。

子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。

思路：
  这道题的数据范围如果直接用第二重循环来找最大的满足条件的递增子序列会超时，贪心的方法也不一定得到最优的结果，因此可以考虑使用线段树来求解。

代码：

struct Node{
    int left=0, right=0, val=0;
    Node(){}
    Node(int left, int right):left(left), right(right){}
};

class SegmentTree{
private:
    vector<int> nums;
    vector<Node> tree;
    int k;
    void build(int u, int left, int right){
        tree[u] = Node(left, right);
        if(left==right) return;
        else{
            int mid = left + (right-left)/2;
            build(2*u, left, mid);
            build(2*u+1, mid+1, right);
        }
    }

    void pushup(int u){
        tree[u].val = max(tree[2*u].val, tree[2*u+1].val);
        if(u>1) pushup(u/2);
    }

public:
    SegmentTree(vector<int>& nums, int k, int maxV):nums(nums.size()),k(k){
        tree.resize(4*maxV);
        build(1, 1, maxV);
        for(int i=0;i<nums.size();++i){
            update(1, nums[i]);
        }
    }

    void update(int u, int val){
        if(tree[u].left == val && tree[u].right == val){
            int preLen = range(1, max(1, val-k), val-1)+1;
            tree[u].val = preLen;
            pushup(u/2);
        }
        else{
            int mid = tree[u].left + (tree[u].right-tree[u].left)/2;
            if(val>mid){
                update(2*u+1, val);
            }
            else{
                update(2*u, val);
            }
        }
    }

    int range(int u, int left, int right){
        if(right<left) return 0;
        if(left==tree[u].left && right==tree[u].right) return tree[u].val;
        else{
            int mid = tree[u].left + (tree[u].right-tree[u].left)/2;
            if(left>mid) return range(2*u+1, left, right);
            else if(right<=mid) return range(2*u, left, right);
            else{
                return max(range(2*u, left, mid), range(2*u+1, mid+1, right));
            }
        }
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums, int k) {
        int maxV = *max_element(nums.begin(), nums.end());
        SegmentTree segmentTree(nums, k, maxV);
        return segmentTree.range(1, 1, maxV);
    }
};

参考文献

[1]. 灵茶山艾府.求解最大子数组和两种方法：前缀和/动态规划（Python/Java/C++/C/Go/JS/Rust）
[2]. 灵茶山艾符.最长公共子序列 编辑距离
[3]. 灵茶山艾符.最长递增子序列
[4]. 灵茶山艾符.线段树优化 DP（Python/Java/C++/Go）

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐