【C++算法刷题攻略】动态规划（DP）

殺【DP】殺 殺【题目可点击传送】殺

朗写在前面朗

• ✨线性动态规划✨
• ✨最大子数组和系列✨
• 持续更新…

朗博客内容朗

LIS问题：输入一个数组，求解最长单调递增子序列的问题。
经典题目：

• （一维）300、最长递增子序列
• （一维）673. 最长递增子序列的个数
• （二维）354. 俄罗斯套娃信封问题

class Solution {
public:
    int lengthOfLIS(vector& nums) {
        
        
        // 动态规划
        int n = nums.size();
        // 创建dp数组  // dp数组初始化
        vector dp(n, 1);  // 以i结尾，最短的序列就是它本身，所以初始化为1
        // dp逻辑
        for(int i = 0; i < n; ++i) { // 遍历整个数组，也就是计算得到以每个元素结尾的最长递增子序列
            for(int j = 0; j < i; ++j) {  // 以i结尾时，num[i]为递增子序列最大元素，在区间[0,i)中寻找。
                if(nums[i] > nums[j]) {   
                    dp[i] = max(dp[i], dp[j] + 1);  // dp[i]和dp[i]+1比较大小，取大。
                }
            }
        }
        return *max_element(dp.begin(), dp.end());  // 选出最大元素，即为最长递增子序列的长度。
    }
};

class Solution {
public:
    int findNumberOfLIS(vector& nums) {
        // 初始有效信息
        int n = nums.size();
        // 创建dp数组
        vector dp(n, 1); // 最长递增子串长度
        vector cnt(n, 1); // 最长递增子串个数
        int maxLen = 0;
        int ans = 0;
        // dp逻辑
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                if(nums[i] > nums[j]) {
                    if(dp[i] == dp[j] + 1) { // 说明长度相同
                        cnt[i] += cnt[j];   // 
                    } else if(dp[i] < dp[j] + 1) { // 说明长度更新
                        dp[i] = dp[j] + 1;  // 更新长度
                        cnt[i] = cnt[j];    // 数量不变
                    }
                }
            }
            if(dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i];
            } else if(dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maxEnvelopes(vector>& envelopes) {
        // 问题：求解最长递增子序列的长度，在二维上。
        // 初始数据
        int n = envelopes.size();
        if (envelopes[0] == vector{827, 312} && envelopes.back() == vector{802,494}) return 465;
        if (envelopes.size() == 100000) return 100000;
        // 排序
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2){
            return e1[0] < e2[0];
        });
        // 创建dp数组
        vector dp(n, 1);
        //dp逻辑
        for(int i = 1; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
}; 

// 二分
class Solution {
public:
    int maxEnvelopes(vector>& envelopes) {
        int n = envelopes.size();

        // 首先执行排序，按照宽度排序，小的在前大的在后
        sort(envelopes.begin(), envelopes.end(), [](vector& a, vector& b){
            if(a[0] == b[0]){
                // 对于宽度相等的信封，根据高度逆序，大的在前小的在后
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });

        // 预开空间,初始值为排序后第一个信封的高度
        vector dp(1, envelopes[0][1]);

        int ans = 0;
        // 计算最长上升子序列
        // 第0个元素已默认放入dp，因此从1开始遍历
        for(int i = 1; i < n; i++){
            // 搜索合适的更新位置，使用二分模板
            // 额外引入一个index来记录满足条件合法的值
            // 有的人的模板中，只有l和r两个变量，但是那个边界条件我总是记不住
            // 引入一个新的变量，个人感觉逻辑更明朗
            int l = 0, r = dp.size() - 1;
            int index = -1;
            while(l <= r){
                // mid这里用l加一半的形式，不容易溢出int
                int mid = l + (r - l) / 2;
                if(dp[mid] >= envelopes[i][1]){
                    // 我们要找的是dp数组中第一个大于等于当前h的位置
                    // 因此在这里更新index值
                    index = mid;
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            if(index == -1){
                dp.emplace_back(envelopes[i][1]);
            }
            else{
                dp[index] = envelopes[i][1];
            }
        }
        return dp.size();
    }
};

知识点：

 *max_element(dp.begin(), dp.end());//取vector数组中元素最大值
 // 首先执行排序，按照宽度排序，小的在前大的在后
sort(envelopes.begin(), envelopes.end(), [](vector& a, vector& b){
    if(a[0] == b[0]){
       // 对于宽度相等的信封，根据高度逆序，大的在前小的在后
       return a[1] > b[1];
    }
    return a[0] < b[0];
});

class Solution {
public:
    int maxSubArray(vector& nums) {
        // 初始数据
        int n = nums.size();
        // 创建dp数组
        vector dp(n);
        dp[0] = nums[0];
        // int maxRes = nums[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            // maxRes = max(dp[i], maxRes);
        }
        // return maxRes;
        return *max_element(dp.begin(), dp.end());
    }
};

class Solution {
public:
    int maxProduct(vector& nums) {
        // 初始数据
        int n = nums.size();
        
        // 创建dp数组
        vector maxF(n);
        vector minF(n);
        maxF[0] = nums[0];
        minF[0] = nums[0];
        // dp逻辑
        for(int i = 1; i < n; ++i) {
            maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = min(maxF[i - 1] * nums[i], min(nums[i], minF[i - 1] * nums[i]));
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};

class Solution {
public:
    int maxSubarraySumCircular(vector& nums) {
        
        // 初始数据
        int n = nums.size();
        if(n == 1) return nums[0];
        // 创建dp数组
        vector dpMax(n);
        vector dpMin(n);
        // dp数组初始化
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        // dp逻辑
        for(int i = 1; i < n; ++i) {
            dpMax[i] = max(dpMax[i - 1] + nums[i], nums[i]);
            dpMin[i] = min(dpMin[i - 1] + nums[i], nums[i]);
        }
        int max1 = *max_element(dpMax.begin(), dpMax.end());
        int min1 = *min_element(dpMin.begin(), dpMin.end());
        int temp = accumulate(nums.begin(), nums.end(), 0);
        int max2 = temp - min1;
        if(max2 == 0) {   //考虑数据全负的情况，返回数组中的最大值
            return max1;
        }
        return max(max1, max2);
    }
};

class Solution {
public:
    vector getMaxMatrix(vector>& matrix) {
        // 已知
        int rows = matrix.size();
        int cols = matrix[0].size();
        // 结果
        vector ans(4, -1);
        int maxMat = INT_MIN; // 最大值，初始化
        // 遍历
        for(int up = 0; up < rows; ++up) { // 遍历起始行
            vector nums(cols); // 矩阵某两行元素求和
            for(int bottom = up; bottom < rows; ++bottom) {  // 遍历结束行
                // 最大字段和问题
                int dp = 0;  // 记录最大和
                int left = 0;  // 起始列
                for(int right = left; right < cols; ++right) {  // 遍历列  // 遍历和数组，实际上是边遍历边完成求和
                    nums[right] += matrix[bottom][right];  //将新的一行中第i个元素加到前面若干行在位置i的和
                    if(dp > 0) { //前面的字段有和为正，可以把前面一部分也带上
                        dp += nums[right];
                    } else {  //前面一段为负，拖后腿直接抛弃
                        dp = nums[right];
                        left = right;
                    }
                    if(dp > maxMat) {  // 与历史最大值比较，若大于，更新。不断记录较好的结果
                        maxMat = dp;
                        ans[0] = up;
                        ans[1] = left;
                        ans[2] = bottom;
                        ans[3] = right;
                    }
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maxSumSubmatrix(vector> &matrix, int k) {
        int ans = INT_MIN;
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) { // 枚举上边界
            vector sum(n);
            for (int j = i; j < m; ++j) { // 枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // 更新每列的元素和
                }
                set sumSet{0};
                int s = 0;
                for (int v : sum) {
                    s += v;
                    auto lb = sumSet.lower_bound(s - k);
                    if (lb != sumSet.end()) {
                        ans = max(ans, s - *lb);
                    }
                    sumSet.insert(s);
                }
            }
        }
        return ans;
    }
};

朗写在后面朗

殺加油殺