跳转至

Dp33

一、动态规划秘籍

动态规划（Dynamic Programming）是一种解决复杂问题的算法思想，适用于求解一类最优化问题。以下是一些动态规划的秘籍：

  1. 确定状态：动态规划问题的第一步是确定问题的状态。状态是指可以描述问题的所有变量的值，通常是一组变量。
  2. 定义状态转移方程：动态规划的核心是状态转移方程，它描述了如何从一个状态转移到另一个状态。状态转移方程的定义通常是一个递归式，表示问题的最优解与子问题的最优解之间的关系。
  3. 确定边界条件：边界条件是指问题的最小子问题的解，也是递归的终止条件。通常情况下，边界条件是已知的，例如，当子问题为空时，递归就可以终止。
  4. 确定计算顺序：动态规划问题的计算顺序可以是自顶向下或自底向上。自顶向下的计算顺序通常是递归的方式，而自底向上的计算顺序通常是使用一个数组或矩阵来存储计算结果。
  5. 优化空间复杂度：在实际应用中，动态规划通常需要存储大量的中间状态。为了减少存储空间，可以采用滚动数组、矩阵压缩等技巧来优化空间复杂度。
  6. 注意细节：在实现动态规划算法时，还需要注意细节。例如，处理边界条件、避免重复计算等。

二、线性dp

​ 线性动态规划（Linear Dynamic Programming）是一类动态规划问题，通常涉及一个序列或字符串，其时间复杂度为O(n2)或O(n)，以下是一些线性动态规划的秘籍：

  1. 确定状态：线性动态规划的第一步是确定状态。通常情况下，状态可以表示为一个数组或矩阵，每个元素表示一个子问题的最优解或状态值。
  2. 定义状态转移方程：状态转移方程通常是一个递推式，用于计算当前状态的最优解或状态值。在线性动态规划中，状态转移方程通常涉及到当前元素和前面元素的状态值或最优解。
  3. 确定边界条件：边界条件是指最小子问题的解，通常是已知的。在线性动态规划中，边界条件通常是初始状态或已知状态。
  4. 优化空间复杂度：在实际应用中，线性动态规划通常需要存储大量的中间状态。为了减少存储空间，可以采用滚动数组等技巧来优化空间复杂度。
  5. 注意细节：在实现线性动态规划算法时，还需要注意一些细节。例如，处理边界条件、避免重复计算等。
  6. 优化时间复杂度：在某些情况下，可以使用滑动窗口等技巧来进一步优化时间复杂度，使其达到O(n)。

2.1 数字三角形

​ 数字三角形（Triangle）是一类经典的动态规划问题，通常给定一个数字三角形，求从顶部到底部的路径中所有数字之和的最大值。以下是一种常见的数字三角形解法：

  1. 状态表示：设f(i,j)表示从顶部到第i行第j列的最大路径和。
  2. 状态转移方程：由于每个状态只能从上一行相邻的两个状态转移而来，因此状态转移方程为f(i,j)=max{f(i-1,j),f(i-1,j-1)}+triangle[i] [j]。
  3. 边界条件：当i=1时，f(i,j)=triangle[i] [j]。
  4. 最优解：最终的最优解是f(n,j)，其中n表示数字三角形的总行数，j表示最后一行的最大值所在的列数。
  5. 计算顺序：根据状态转移方程，可以使用自底向上的方式计算最大路径和。

下面是C++代码实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int maxPathSum(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<int> dp(triangle[n-1]); // 初始化为最后一行的值
    for (int i = n-2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            dp[j] = max(dp[j], dp[j+1]) + triangle[i][j];
        }
    }
    return dp[0]; // 返回最大路径和
}

​ 在上述代码中，使用一个一维数组dp来存储每行的最大路径和，可以通过滚动数组进一步优化空间复杂度。时间复杂度为O(n2)，空间复杂度为O(n)。

2.2 最长上升子序列

​ 最长上升子序列（Longest Increasing Subsequence，LIS）是一类经典的动态规划问题，通常给定一个序列，求其中最长的严格递增子序列的长度。以下是几种常见的LIS解法：

  1. 动态规划：设dp[i]表示以第i个元素结尾的最长上升子序列的长度，则状态转移方程为：

dp[i] = max(dp[j]+1)，其中j<i且nums[j]<nums[i]。

最终的最长上升子序列的长度为dp数组中的最大值。

时间复杂度为O(n2)，空间复杂度为O(n)。

  1. 贪心算法 + 二分查找：该算法的基本思想是维护一个递增的序列，其中最后一个元素是序列中的最大值，每次遍历到一个新元素时，如果它大于当前序列的最大值，则直接将其插入到序列末尾；否则，使用二分查找找到一个位置，将当前元素插入到该位置，同时更新当前位置的值。最终序列的长度即为最长上升子序列的长度。

时间复杂度为O(nlogn)，空间复杂度为O(n)。

  1. Patience Sorting：该算法的基本思想是将原序列拆分成若干个子序列，每个子序列是一个递减的序列。然后，对每个子序列维护一个堆（或栈），每次将新元素插入到堆（或栈）的顶部，直到所有元素都被插入完毕。最终，按照堆（或栈）的顺序将所有元素重新组合成一个新的序列，该序列就是最长上升子序列。

时间复杂度为O(nlogn)，空间复杂度为O(n)。

以下是动态规划解法的C++代码示例，以最长上升子序列（LIS）问题为例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // 初始化为1
    int max_len = 1;
    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);
            }
        }
        max_len = max(max_len, dp[i]); // 更新最大长度
    }
    return max_len;
}

​ 在上述代码中，使用一个一维数组dp来存储以每个元素结尾的最长上升子序列的长度。对于每个元素i，遍历之前的所有元素j，如果满足nums[i]>nums[j]，则更新dp[i]为dp[j]+1。最终，最长上升子序列的长度为dp数组中的最大值。时间复杂度为O(n^2)，空间复杂度为O(n)。

​ 需要注意的是，动态规划解法的代码可能会比较简洁，但是时间复杂度较高，对于规模较大的问题可能会超时。因此，需要根据具体问题的规模和要求选择合适的算法和数据结构。

2.3 最长公共子序列

​ 最长公共子序列（Longest Common Subsequence，LCS）问题是一类经典的动态规划问题，通常给定两个序列，求它们的最长公共子序列的长度。以下是几种常见的LCS解法：

  1. 动态规划：设dp[i][j]表示序列1中前i个元素和序列2中前j个元素的最长公共子序列的长度，则状态转移方程为：

dp[i] [j] = dp[i-1] [j-1] + 1，当nums1[i-1] == nums2[j-1]；

dp[i] [j] = max(dp[i-1] [j], dp[i] [j-1])，当nums1[i-1] != nums2[j-1]。

最终的最长公共子序列的长度为dp[m] [n]，其中m和n分别为序列1和序列2的长度。

时间复杂度为O(mn)，空间复杂度为O(mn)。

  1. 空间优化：由于每次转移只需要用到上一行和上一列的信息，因此可以使用滚动数组或二维数组中的一行或一列来存储状态，从而将空间复杂度降到O(min(m,n))。

时间复杂度为O(mn)，空间复杂度为O(min(m,n))。

  1. 最长公共子串：该算法的基本思想是将两个序列拼接成一个字符串，并求该字符串的最长公共子串的长度。在拼接后的字符串中，最长公共子串必须是一段连续的子串。

时间复杂度为O(mn)，空间复杂度为O(mn)。

以下是动态规划解法的C++代码示例，以最长公共子序列（LCS）问题为例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 初始化为0
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++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[m][n];
}

​ 在上述代码中，使用一个二维数组dp来存储两个序列的最长公共子序列的长度。对于每个位置(i,j)，如果text1[i-1]等于text2[j-1]，则dp[i] [j]等于dp[i-1] [j-1]+1；否则，dp[i] [j]等于dp[i-1] [j]和dp[i] [j-1]中的较大值。最终的最长公共子序列的长度为dp[m] [n]，其中m和n分别为text1和text2的长度。时间复杂度为O(mn)，空间复杂度为O(mn)。

​ 需要注意的是，动态规划解法的代码可能会比较简洁，但是时间复杂度较高，对于规模较大的问题可能会超时。因此，需要根据具体问题的规模和要求选择合适的算法和数据结构。

2.4 最大连续字段和

​ 最大连续子数组和（Maximum Subarray）问题是一类经典的动态规划问题，通常给定一个数组，求其最大的连续子数组的和。以下是几种常见的解法：

  1. 动态规划：设dp[i]表示以第i个元素结尾的最大连续子数组和，则状态转移方程为：

dp[i] = max(dp[i-1] + nums[i], nums[i])

其中，dp[0] = nums[0]。最终的结果为max(dp[i])，其中0 <= i < n。

时间复杂度为O(n)，空间复杂度为O(n)。

  1. 空间优化：由于每次转移只需要用到上一个状态的信息，因此可以使用一个变量maxSum来存储最大的连续子数组和，一个变量curSum来存储当前的连续子数组和，从而将空间复杂度降到O(1)。

时间复杂度为O(n)，空间复杂度为O(1)。

  1. 分治法：将数组分为左半部分、右半部分和跨越中间的子数组三部分。左半部分、右半部分的最大连续子数组和可以递归求解，跨越中间的子数组的最大连续子数组和可以通过计算以中间元素为起点的最大连续子数组和和以中间元素为终点的最大连续子数组和来求得。最终的结果为三个子数组中最大的连续子数组和。

时间复杂度为O(nlogn)，空间复杂度为O(logn)。

以下是动态规划解法的C++代码示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 0); // 初始化为0
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = max(dp[i-1]+nums[i], nums[i]);
        res = max(res, dp[i]);
    }
    return res;
}

​ 在上述代码中，使用一个数组dp来存储以每个元素结尾的最大连续子数组和。对于每个位置i，如果dp[i-1]+nums[i]大于nums[i]，则dp[i]等于dp[i-1]+nums[i]；否则，dp[i]等于nums[i]。最终的结果为dp数组中的最大值。时间复杂度为O(n)，空间复杂度为O(n)。

三、区间dp

​ 区间DP是动态规划中的一种常见思想，它通常用于处理区间问题，即对于一个序列，需要对其某个子区间进行操作，例如求子区间的最大值、最小值、最长公共子序列等等。

以下是区间DP的一些常见思路和技巧：

  1. 状态表示：通常使用二维数组dp[i] [j]表示从i到j的子区间的最优解。如果问题还需要求区间的划分方案，则可以使用三维数组dp[i][j][k]表示从i到j的子区间在第k个位置进行划分时的最优解。

  2. 状态转移方程：通常情况下，区间DP的状态转移方程是由子区间的最优解推导出父区间的最优解，可以通过枚举区间中的某个位置k来实现。例如，对于求解最长公共子序列问题，可以使用以下状态转移方程：

dp[i] [j] = dp[i-1] [j-1] + 1 if s1[i] == s2[j] = max(dp[i-1] [j], dp[i] [j-1]) otherwise

  1. 边界条件：通常情况下，需要对dp数组进行一些初始化操作。例如，对于求解最长公共子序列问题，需要将dp数组的第一行和第一列初始化为0。

  2. 计算顺序：由于区间DP需要从小区间向大区间进行状态转移，因此计算顺序通常是从小到大。可以使用长度作为外循环，位置作为内循环，以便满足计算顺序的要求。

  3. 状态压缩：由于区间DP的状态通常较大，因此可以考虑对状态进行压缩。例如，对于求解最长公共子序列问题，可以只使用两个一维数组dp1和dp2来存储当前行和上一行的状态，从而将空间复杂度降为O(n)。

以下是区间DP求解最长回文子序列问题的C++代码示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n-1; i >= 0; --i) {
        dp[i][i] = 1;
        for (int j = i+1; j < n; ++j) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
}

3.1 游艇租赁问题

游艇租赁问题是一个经典的优化问题，通常被称为背包问题的变体。该问题描述如下：给定一定数量的游艇，每艘游艇有不同的租金和载重量，以及一个最大载重量限制，求在不超过最大载重量限制的情况下，如何租用游艇能够使租金最大化。

这个问题可以使用动态规划的思想进行求解，以下是一种常见的解法：

  1. 状态表示：使用二维数组dp[i][j]表示前i艘游艇中，总载重不超过j的情况下能够得到的最大租金。

  2. 状态转移方程：考虑第i艘游艇，可以选择租用或不租用。如果租用第i艘游艇，则最大租金为dp[i-1] [j-w[i]] + v[i]，其中w[i]和v[i]分别表示第i艘游艇的载重量和租金；如果不租用第i艘游艇，则最大租金为dp[i-1] [j]。因此，状态转移方程为：

dp[i] [j] = max(dp[i-1] [j-w[i]] + v[i], dp[i-1] [j])

  1. 边界条件：dp[0] [j] = 0，dp[i] [0] = 0。

  2. 计算顺序：由于每个状态只依赖于上一行的状态，因此可以使用滚动数组来优化空间复杂度，将二维数组转化为一维数组。具体地，可以将状态数组的第一维变为i%2，将状态转移方程中的dp[i-1]改为dp[(i-1)%2]，从而使得计算顺序从小到大进行。

  3. 最终结果：最大租金为dp[n%2] [maxWeight]，其中n表示游艇的数量。

以下是该问题的C++代码实现示例：

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int maxRent(vector<int>& weights, vector<int>& rents, int maxWeight) {
    int n = weights.size();
    vector<int> dp(maxWeight+1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = maxWeight; j >= weights[i-1]; --j) {
            dp[j] = max(dp[j], dp[j-weights[i-1]] + rents[i-1]);
        }
    }
    return dp[maxWeight];
}

注意：这里的weights和rents数组下标从0开始，与代码中的i和j的范围相对应。

四、背包问题

​ 背包问题是一个经典的动态规划问题，通常被描述为：有一个容量为V的背包和n个物品，每个物品有一个重量w和一个价值v。要求选取若干个物品放入背包中，使得背包能够装下的物品的总价值最大。

以下是一些解决背包问题的秘籍：

1、0-1背包问题

​ 0-1背包问题指的是每个物品要么选中，要么不选中，不能选择一部分。该问题可以使用二维数组进行动态规划求解，其中dp[i] [j]表示前i个物品放入容量为j的背包中能够获得的最大价值。状态转移方程为：

dp[i] [j] = max(dp[i-1] [j], dp[i-1] [j-w[i]]+v[i])，其中w[i]和v[i]分别表示第i个物品的重量和价值。

2、完全背包问题

​ 完全背包问题指的是每个物品可以选取无限次。该问题可以使用一维数组进行动态规划求解，其中dp[j]表示容量为j的背包能够获得的最大价值。状态转移方程为：

dp[j] = max(dp[j], dp[j-w[i]]+v[i])，其中w[i]和v[i]分别表示第i个物品的重量和价值。

3、多重背包问题

​ 多重背包问题指的是每个物品最多选取mi次。该问题可以使用二进制拆分和二维数组进行动态规划求解，其中dp[i] [j]表示前i个物品放入容量为j的背包中能够获得的最大价值。状态转移方程为：

dp[i] [j] = max(dp[i-1] [j-k * w[i]]+k * v[i])，其中k的范围为0到min(mi, j/w[i])。

4、混合背包问题

​ 混合背包问题指的是每个物品有自己的选取数量限制，可以选取0次、1次或多次。该问题可以使用多重背包问题和01背包问题的结合进行求解。

五、树形dp

树形DP是指在一棵树上进行动态规划的过程，常常用于解决一些与树相关的问题。以下是一些解决树形DP问题的秘籍：

1、树的遍历顺序

​ 在进行树形DP时，需要确定树的遍历顺序，常见的遍历方式包括DFS和BFS。DFS方式下，一般使用递归或者栈来实现，可以使用一个数组记录每个节点的访问状态。BFS方式下，一般使用队列来实现，需要使用一个数组记录每个节点的父节点。

2、状态的定义

​ 树形DP的状态通常与节点有关，可以使用一个数组来存储每个节点的状态。对于每个节点，需要定义它的状态以及状态转移方程。

3、状态转移方程

​ 树形DP的状态转移方程通常与节点的父节点、子节点有关。对于每个节点，需要考虑它的父节点、子节点以及它本身对它的状态的影响，然后推导出它的状态转移方程。

4、树形DP的分类

​ 常见的树形DP问题包括树的直径、树的重心、树的最大独立集、树的最小点覆盖等。树形DP问题可以分为两类：自顶向下和自底向上。自顶向下的树形DP通常使用DFS遍历，从根节点开始，先求出子节点的状态，再根据子节点的状态计算父节点的状态。自底向上的树形DP通常使用BFS遍历，先计算出叶子节点的状态，然后根据子节点的状态计算出父节点的状态。

六、数位dp

​ 数位DP是指在数字的各个位上进行动态规划的过程，常用于解决一些与数字相关的问题，如计数、排列、组合等问题。以下是一些解决数位DP问题的秘籍：

1、状态的定义

​ 数位DP的状态通常与数字的位数有关，可以使用一个数组来存储每个位的状态。对于每个位，需要定义它的状态以及状态转移方程。

2、状态转移方程

​ 数位DP的状态转移方程通常与数字的各个位有关。对于每个位，需要考虑它的前一位和后一位以及它本身对它的状态的影响，然后推导出它的状态转移方程。

3、数位DP的分类

​ 常见的数位DP问题包括计数问题、排列问题、组合问题等。数位DP问题可以分为两类：从高位到低位和从低位到高位。从高位到低位的数位DP通常使用递归来实现，从高位开始计算，计算完当前位之后再递归到下一位。从低位到高位的数位DP通常使用循环来实现，从低位开始计算，计算完当前位之后再计算上一位。

4、注意边界条件

​ 在进行数位DP时，需要注意边界条件。例如，在计数问题中，需要考虑当前数字与目标数字大小关系；在排列问题中，需要考虑是否有重复数字等。

七、状态压缩dp

​ 状态压缩DP是一种使用二进制状态压缩的动态规划算法，用于解决一些具有状态数量巨大的问题，如旅行商问题、最小路径覆盖问题等。以下是一些解决状态压缩DP问题的秘籍：

1、状态的表示

​ 状态压缩DP的核心是对状态的表示，通常使用二进制数表示。对于n个元素的状态，使用n位二进制数表示，其中第i位表示第i个元素的状态。例如，对于一个长度为n的字符串，可以使用一个n位二进制数表示每个字符的状态，1表示已经选中，0表示未选中。

2、状态转移方程

​ 状态压缩DP的状态转移方程通常与状态的表示有关，对于每个状态，需要考虑它的前一个状态以及它的状态转移方程。通常采用位运算进行状态的转移，如按位或、按位与、按位异或等。

3、状态的枚举

​ 在状态压缩DP中，通常需要枚举所有可能的状态。对于n个元素，状态的数量为2的n次方，通常使用循环或递归来枚举所有状态。

4、优化空间复杂度

​ 由于状态数量巨大，状态压缩DP常常面临空间复杂度过高的问题。为了优化空间复杂度，可以使用滚动数组、状态压缩等技巧。例如，对于一个二维的状态，可以使用一维数组来存储状态，每次只保留上一行或上一列的状态。

八、插头dp

​ 插头DP是一种经典的图论问题求解方法，它的核心思想是将一个图分解成若干个简单的子图，通过求解子图的最优解，逐步推导出整个图的最优解。以下是一些解决插头DP问题的秘籍：

1、插头的表示

​ 在插头DP中，通常使用二进制数表示每个节点的状态，其中第i位表示节点i的出度，1表示节点i有一条出边，0表示节点i没有出边。每个节点的状态可以看作一个长度为n的二进制数，其中n为图中节点的数量。

2、插头的连接

​ 在插头DP中，需要将节点之间的插头连接起来，形成一个有向图。通常使用位运算进行插头的连接，如按位与、按位或、按位异或等。

3、插头DP的状态转移方程

​ 插头DP的状态转移方程通常与插头的表示和连接有关，对于每个状态，需要考虑它的前一个状态以及它的状态转移方程。通常使用矩阵乘法进行状态的转移，矩阵的每一行表示一个状态，矩阵的乘积表示多个状态的组合。

4、插头的枚举

​ 在插头DP中，需要枚举所有可能的插头状态。对于n个节点，每个节点有两种状态，插头的状态数量为2的n次方，需要使用循环或递归来枚举所有状态。

5、优化时间复杂度

​ 由于插头的状态数量巨大，插头DP常常面临时间复杂度过高的问题。为了优化时间复杂度，可以使用矩阵快速幂等技巧，将矩阵的乘积转化为矩阵的幂次运算。

九、动态规划优化

动态规划是一种常见的算法设计技巧，可以解决很多优化问题。以下是一些动态规划优化的秘籍：

1、状态压缩

​ 状态压缩是动态规划优化的重要手段之一。在状态空间较大的情况下，可以使用二进制数来表示状态，减少状态数量。例如，当状态只和前一个状态有关时，可以使用滚动数组来节省空间。

2、前缀和和差分

​ 前缀和和差分是解决一类区间问题的常用技巧。通过预处理数组的前缀和或差分，可以减少重复计算，提高动态规划的效率。例如，在计算子区间和时，可以使用前缀和来计算，而不需要每次重新计算子区间的和。

3、二分答案

​ 在一些求最优解的问题中，可以使用二分答案来优化动态规划的效率。通过二分答案来确定最优解的范围，然后使用动态规划求解。例如，在求最小值或最大值时，可以使用二分答案来确定最优解的范围，然后使用动态规划求解。

4、单调队列和单调栈

​ 单调队列和单调栈是处理一类单调性问题的常用技巧。它们可以用来快速找到一些最大值或最小值，并且可以在O(1)时间内插入或删除元素。在一些求最优解的问题中，可以使用单调队列或单调栈来优化动态规划的效率。

5、贪心策略

​ 在一些特殊的情况下，可以使用贪心策略来优化动态规划的效率。例如，在求最小值或最大值时，可以使用贪心策略来选择最优的决策。但需要注意的是，贪心策略可能不能得到最优解，需要根据具体情况进行选择。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用