0502线性动态规划

单串线性 DP 问题

如果状态包含多个维度，但是每个维度上都是线性划分的阶段，也属于线性 DP。比如背包问题、区间 DP、数位 DP 等都属于线性 DP。

线性 DP 问题的划分方法有多种方式。

如果按照「状态的维度数」进行分类，我们可以将线性 DP 问题分为：一维线性 DP 问题、二维线性 DP 问题，以及多维线性 DP 问题。
如果按照「问题的输入格式」进行分类，我们可以将线性 DP 问题分为：单串线性 DP 问题、双串线性 DP 问题、矩阵线性 DP 问题，以及无串线性 DP 问题。

最长递增子序列

分析

  1. 划分阶段：按照子序列的结尾位置进行阶段划分。
  2. 定义状态：定义状态dp[i]表示为：以nums[i]结尾的最长递增子序列长度。
  3. 状态转移方程：一个较小的数后边如果出现一个较大的数，则会形成一个更长的递增子序列。$dp[i] = \max(dp[i], dp[j]+1), 0 \leq j \leq i \And nums[j] < nums[i]$
  4. 初始条件：默认状态下，把数组中的每个元素都作为长度为1的递增子序列。
  5. 最终结果：返回dp中的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        // 返回结果
        int res = 0;
        for(int i = 0; i < n; i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(n)

最大子数组和

分析

  1. 划分阶段：按照子序列的结尾位置进行阶段划分。
  2. 定义状态：dp[i]表示以nums[i]结尾的最大子数组和。
  3. 状态转移：$dp[i] = max(0, dp[i-1]) + nums[i]$
  4. 初始条件：$dp[0] = nums[0]$
  5. 返回结果：dp最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        for(int i = 1; i < n; i++){
            dp[i] = max(dp[i-1], 0) + nums[i];
        }
        // 返回结果
        int res = INT_MIN;
        for(int i = 0; i < n; i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

动态规划 + 滚动优化

因为dp[i]只和dp[i-1]和当前元素nums[i]相关，我们也可以使用一个变量subMax来表示以第i-1个数结尾的连续子数组的最大和。然后使用res来保存全局中最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int subMax = nums[0];
        int res = nums[0];
        for(int i = 1; i < n; i++){
            subMax = max(subMax, 0) + nums[i];
            res = max(subMax, res);
        }
        return res;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

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

分析

  1. 划分阶段：按照斐波那契式子序列相邻两项的结尾位置进行阶段划分。
  2. 定义状态：表示为：以arr[i]、arr[j]为结尾的斐波那契式子序列的最大长度。
  3. 状态转移方程：$dp[j][k] = max_{(A[i] + A[j] = A[k], \quad i < j < k)}(dp[i][j] + 1)$。
  4. 初始条件：dp[i][j] = 2
  5. 返回结果：$res \geq 3$，返回res，否则返回0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        // 定义状态数组
        vector<vector<int>> dp(n, vector<int>(n, 2));
        // 映射成哈希表
        unordered_map<int, int> hash;
        for(int i = 0; i < n; i++){
            hash[arr[i]] = i;
        }
        // 计算
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                // 获取索引
                int sum = arr[i] + arr[j];
                if(hash.find(sum) != hash.end()){
                    int k = hash[sum];
                    dp[j][k] = max(dp[j][k], dp[i][j]+1);
                    res = max(res, dp[j][k]);
                }

            }
        }
        return res;
    }
};
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

双串线性DP问题

双串线性DP问题

最长公共子序列

分析

  1. 划分阶段：按照两个字符串的结尾位置进行阶段划分。
  2. 定义状态：dp[i][j]等于以text1前i个字符和text2以前j个字符的子序列长度。
  3. 状态转移方程：Alt text
  4. 初始条件：dp[0][j] = dp[i][0] = 0
  5. 返回结果：dp[size1][size2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // 定义状态数组
        int size1 = text1.length();
        int size2 = text2.length();
        vector<vector<int>> dp(size1+1, vector<int>(size2+1));
        // 循环遍历
        for(int i = 1; i <= size1; i++){
            for(int j = 1; j <= size2; j++){
                // 如果子字符串的最后一个字符相等
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[size1][size2];
    }
};
  • 时间复杂度：$O(n \times m)$
  • 空间复杂度：$O(n \times m)$

最长重复子数组

分析

  1. 划分阶段：按照子数组结尾位置进行阶段划分。
  2. 定义状态：dp[i][j]表示nums1前i个数字和nums2的前j个数字的最长公共子数组长度。
  3. 状态转移方程：
    • 如果nums1[i-1] == nums2[j-1]，那么dp[i][j] = dp[i-1][j-1]+1；
    • 否则，dp[i][j] = 0。
  4. 初始条件：dp[0][j] = dp[i][0] = 0
  5. dp[i][j]中的最大值，可以在循环中用一个变量保存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        // 定义状态数组
        int size1 = nums1.size();
        int size2 = nums2.size();
        vector<vector<int>> dp(size1+1, vector<int>(size2+1));
        // 循环遍历
        int res = 0;
        for(int i = 1; i <= size1; i++){
            for(int j = 1; j <= size2; j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
};
  • 时间复杂度：$O(n \times m)$。
  • 空间复杂度：$O(n \times m)$。

编辑距离

分析

  1. 划分阶段：按照两个字符串的结尾位置进行阶段划分。
  2. 定义状态：dp[i][j]表示所使用的最小操作数。
  3. 状态转移数组：
    • 如果word1[i-1] == word[j-1]，无需操作，dp[i][j] = dp[i-1][j-1]
    • 否则，dp[i][j] = min(dp[i-1][j](插入), dp[i][j-1](删除), dp[i-1][j-1](替换)) + 1
  4. 初始条件：
    • dp[0][j]=j，当word1长度为0，word2长度为j，需要执行j次插入操作。
    • 同理dp[i][0] = i
  5. 返回结果：dp[size1][size2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int minDistance(string word1, string word2) {
        // 定义状态数组
        int size1 = word1.size();
        int size2 = word2.size();
        vector<vector<int>> dp(size1+1, vector<int>(size2+1));
        // 初始化
        for(int j = 0; j <= size2; j++){
            dp[0][j] = j;
        }
        for(int i = 0; i <= size1; i++){
            dp[i][0] = i;
        }
        // 循环遍历
        for(int i = 1; i <= size1; i++){
            for(int j = 1; j <= size2; j++){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
            
        }
        return dp[size1][size2];
    }
};
  • 时间复杂度：$O(n \times m)$
  • 空间复杂度：$O(n \times m)$

https://github.com/datawhalechina/leetcode-notes/blob/main/docs/ch05/05.02/05.02.06-Exercises.md

最大正方形

分析

  1. 划分阶段：按照正方形的右下角坐标进行阶段划分。
  2. 定义状态：dp[i][j]表示以矩阵位置(i,j)为右下角，且值包含1的正方形的最大边长。
  3. 状态转移方程：
    • matrix[i][j] == 0， 则dp[i][j] = 0
    • 否则，dp[i][j]由上侧、左侧、左上方共同约束，即dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  4. 初始条件：dp[i][j] = 0；边界条件：i == 0 || j == 0，如果matrix[i][j] == 1，则dp[i][j] = 1。
  5. 返回结果：dp中的最大值的平方。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        // 定义状态数组
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        // 循环遍历
        int res = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }
                    else{
                        dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                    }
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res * res;
    }
};
  • 时间复杂度：$O(m \times n)$
  • 空间复杂度：$O(m \times n)$

整数拆分

分析

  1. 划分阶段：按照正整数进行划分。

  2. 定义状态：dp[i]表示将正整数i拆分成至少2个正整数的和之后，这些正整数的最大乘积。

  3. 状态转移方程：
    当$i \geq 2$时，假设正整数i拆分出的第一个整数为$j, 1 \leq j < i$：

    • 将i拆分成j和i-j的和，且i-j不再拆分为多个正整数，此时乘积为：$j \times (i - j)$。
    • 将i拆分成j和i-j的和，且i-j继续拆分为多个正整数，此时乘积为：$j \times dp[i-j]$

    dp[i]取其中较大值。

  4. 初始条件：dp[0] = dp[1] = 0。

  5. 返回结果：dp[n]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int integerBreak(int n) {
        // 定义状态数组
        vector<int> dp(n + 1);
        // 循环遍历
        for(int i = 2; i <= n; i++){
            for(int j = 1; j < i; j++){
                dp[i] = max(dp[i], max(j * (i-j), j * dp[i-j]));
            }
        }
        return dp[n];
    }
};
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(n)

只有两个键的键盘

分析

  1. 划分阶段：按照字符 ‘A’ 的个数进行阶段划分。
  2. 定义状态：dp[i]表示出现i个字符’A’所需要的最小操作次数。
  3. 状态转移方程：$dp[i] = min_{j | i}(dp[i], dp[j] + \frac{i}{j}, dp[\frac{i}{j}] + j)$。
  4. 初始条件：dp[1] = 0.
  5. 返回结果：dp[n]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1);
        for (int i = 2; i <= n; ++i) {
            dp[i] = INT_MAX;
            for (int j = 1; j * j <= i; ++j) {
                if (i % j == 0) {
                    dp[i] = min(dp[i], dp[j] + i / j);
                    dp[i] = min(dp[i], dp[i / j] + j);
                }
            }
        }
        return dp[n];
    }
};
  • 时间复杂度：$O(n \sqrt{n})$
  • 空间复杂度：O(n)

剩余题目

算法笔记 > 动态规划
#leetcode-notes
0502线性动态规划
http://example.com/2024/09/26/posts/0502线性动态规划/
作者
Xuan Yang
发布于
2024年9月26日
许可协议