动态规划三-阿里云开发者社区

动态规划的优化

引入

给定n 个二元组(x,yi),(x2,y2)… (Xn,yn)，已经按照x从小到大排好序了

第一步优化

第二步优化

第三步优化

重点来了，请问对于每个i，你都计算了哪些j和哪些算式?

这里有大量的冗余!

y1一X，y2一X，y3一x3的最大值明明已经在i =4的时候算过了，i =5为啥还要再算一遍呢?记temp = max y1一X1， y2- X2，y3一x3}

i =5时我们只需要计算max(temp， y4 -X4)

对于每个i，我们只需要让已有的temp与最新的“候选项”yi-1-xi-1取max !

O(n)代码

动态规划的转移优化思想

刚才我们完成上面的优化，主要依靠两点:

分离i和j。与i有关的式子放一边，与j有关的式子放一边，不要互相干扰。
观察内层循环变量j的取值范围随着外层循环变量的变化情况

在动态规划中经常遇到类似的式子，i是状态变量，j是决策变量

分离状态变量和决策变量。当循环多于两重时，关注最里边的两重循环，把外层看作定值。
对于一个状态变量，决策变量的取值范围称为“决策候选集合”，观察这个集合随着状态变量
的变化情况

一旦发现冗余，或者有更高效维护“候选集合”的数据结构，就可以省去一层循环扫描!

进一步思考

把上面的问题形象化

你甚至可以发现它可以变成“树的直径”问题

×是树的主干

每个y都是树的分支

1499.满足不等式的最大值

https://leetcode.cn/problems/max-value-of-equation/

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        SegmentTree tree(points);
        int res = INT_MIN;
        for(int j = 1; j < points.size(); j ++){
            // 找到横坐标 >= points[j][0] - k 的第一个索引 i
            int i = binary_search(points, j, points[j][0] - k);
            // 使用线段树求出 [i, j - 1] 区间的最大的 y - x 的值来更新答案
            if(i < j)
                res = max(res, points[j][1] + points[j][0]+ tree.query(i, j - 1));
        }
        return res;
    }
private:
    // 使用二分搜索找到 points[0...r] 区间中横坐标 >= x 的第一个索引
    int binary_search(const vector<vector<int>>& points, int r, int x){
        int l = 0;
        while(l < r){
            int mid = (l + r) / 2;
            if(points[mid][0] < x) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

线段树部分如下：

class SegmentTree{
private:
    int n;
    vector<int> data, tree;
public:
    SegmentTree(const vector<vector<int>>& points) : n(points.size()), data(n), tree(4 * n){
        for(int i = 0; i < n; i ++)
            data[i] = points[i][1] - points[i][0];
        buildSegTree(0, 0, n - 1);
    }
    int query(int l, int r){
        return query(0, 0, n - 1, l, r);
    }
private:
    void buildSegTree(int treeID, int l, int r){
        if(l == r){
            tree[treeID] = data[l];
            return;
        }
        int mid = (l + r) / 2;
        buildSegTree(treeID * 2 + 1, l, mid);
        buildSegTree(treeID * 2 + 2, mid + 1, r);
        tree[treeID] = max(tree[treeID * 2 + 1], tree[treeID * 2 + 2]);
        return;
    }
    int query(int treeID, int l, int r, int ql, int qr){
        if(ql == l && qr == r)
            return tree[treeID];
        int mid = (l + r) / 2;
        if(qr <= mid) return query(treeID * 2 + 1, l, mid, ql, qr);
        else if(ql > mid) return query(treeID * 2 + 2, mid + 1, r, ql, qr);
        int resl = query(treeID * 2 + 1, l, mid, ql, mid);
        int resr = query(treeID * 2 + 2, mid + 1, r, mid + 1, qr);
        return max(resl, resr);
    }
};

思路二：使用优先队列

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        priority_queue<pair<int, int>> pq;
        // 初始放入第一个点的信息
        pq.push({points[0][1] - points[0][0], points[0][0]});
        int res = INT_MIN;
        for(int i = 1; i < points.size(); i ++){
            // 将优先队列队头不符合条件的点扔掉
            while(!pq.empty() && points[i][0] - pq.top().second > k) pq.pop();
            // 使用优先队列队首元素信息更新解
            if(!pq.empty())
                res = max(res, points[i][1] + points[i][0] + pq.top().first);
            // 将当前点的信息放入优先队列
            pq.push({points[i][1] - points[i][0], points[i][0]});
        }
        return res;
    }
};

思路三：使用红黑树

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        set<pair<int, int>> tree;
        // 初始放入第一个点的信息
        tree.insert({points[0][1] - points[0][0], points[0][0]});
        int res = INT_MIN, j = 0;
        for(int i = 1; i < points.size(); i ++){
            // 删除红黑树中不满足条件的数据
            while(j < i && points[i][0] - points[j][0] > k){
                tree.erase({points[j][1] - points[j][0], points[j][0]});
                j ++;
            }
            // 使用红黑树最大元素信息更新解
            if(!tree.empty())
                res = max(res, points[i][1] + points[i][0] + tree.rbegin()->first);
            // 将当前点的信息放入红黑树
            tree.insert({points[i][1] - points[i][0], points[i][0]});
        }
        return res;
    }
};

完全把红黑树当优先队列用的代码如下（C++）：

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        set<pair<int, int>> tree;
        // 初始放入第一个点的信息
        tree.insert({points[0][1] - points[0][0], points[0][0]});
        int res = INT_MIN;
        for(int i = 1; i < points.size(); i ++){
            // 取出红黑树中的最大 y - x 值，如果不满足约束，则删除
            while(!tree.empty() && points[i][0] - tree.rbegin()->second > k)
                tree.erase(--tree.end());
            // 使用红黑树最大元素信息更新解
            if(!tree.empty())
                res = max(res, points[i][1] + points[i][0] + tree.rbegin()->first);
            // 将当前点的信息放入红黑树
            tree.insert({points[i][1] - points[i][0], points[i][0]});
        }
        return res;
    }
};

思路四：使用单调队列

class Solution {
public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        deque<pair<int, int>> dq;
        // 初始放入第一个点的信息
        dq.push_front({points[0][1] - points[0][0], points[0][0]});
        int res = INT_MIN;
        for(int i = 1; i < points.size(); i ++){
            // 对队列首不符合约束的点删除
            while(!dq.empty() && points[i][0] - dq.front().second > k)
                dq.pop_front();
            // 根据队首最大元素信息更新解
            if(!dq.empty())
                res = max(res, points[i][1] + points[i][0] + dq.front().first);
            // 把队列尾的比当前 y - x 还小的元素删除
            while(!dq.empty() && dq.back().first <= points[i][1] - points[i][0])
                dq.pop_back();
            // 将当前点的信息加入队列
            dq.push_back({points[i][1] - points[i][0], points[i][0]});
        }
        return res;
    }
};

918.环形了数组的最大和

https://leetcode.cn/problems/maximum-sum-circular-subarray/

class Solution {
public:
        int maxSubarraySumCircular(vector<int>& A) {
        int total = 0, maxSum = A[0], curMax = 0, minSum = A[0], curMin = 0;
        for (int& a : A) {
            curMax = max(curMax + a, a);
            maxSum = max(maxSum, curMax);
            curMin = min(curMin + a, a);
            minSum = min(minSum, curMin);
            total += a;
        }
        return maxSum > 0 ? max(maxSum, total - minSum) : maxSum;
    }
};

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        vector<int> cp(nums), sums(1, 0);
        for (auto& l : cp) nums.push_back(l);
        for (auto& l : nums) sums.push_back(sums.back() + l);
        deque<int> dq;
        dq.push_back(0);
        int ans = sums[1];
        for (int i = 1; i < sums.size(); i ++ ) {
            while (!dq.empty() && i - dq.front() > cp.size()) dq.pop_front();
            ans = max(ans, sums[i] - sums[dq.front()]);
            while (!dq.empty() && sums[dq.back()] >= sums[i]) dq.pop_back();
            dq.push_back(i);  
        }
        return ans;
    }
};

给定一个由整数数组A表示的环形数组C，求C的非空子数组的最大可能和

请大家回顾之前学过的:

最大子序和
“滚动型”环形动态规划的处理方法

这道题是一个“区间型”环形动态规划

区间动态规划

312.戳气球

https://leetcode.cn/problems/burst-balloons/

class Solution {
public:
    vector<vector<int>> rec;
    vector<int> val;
public:
    int solve(int left, int right) {
        if (left >= right - 1) {
            return 0;
        }
        if (rec[left][right] != -1) {
            return rec[left][right];
        }
        for (int i = left + 1; i < right; i++) {
            int sum = val[left] * val[i] * val[right];
            sum += solve(left, i) + solve(i, right);
            rec[left][right] = max(rec[left][right], sum);
        }
        return rec[left][right];
    }
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        val.resize(n + 2);
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        val[0] = val[n + 1] = 1;
        rec.resize(n + 2, vector<int>(n + 2, -1));
        return solve(0, n + 1);
    }
};

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> rec(n + 2, vector<int>(n + 2));
        vector<int> val(n + 2);
        val[0] = val[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    int sum = val[i] * val[k] * val[j];
                    sum += rec[i][k] + rec[k][j];
                    rec[i][j] = max(rec[i][j], sum);
                }
            }
        }
        return rec[0][n + 1];
    }
};

C++ Code

1000.合并石头的最低成本

https://leetcode.cn/problems/minimum-cost-to-merge-stones/

class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        int n = stones.size();
        if ((n - 1) % (K - 1) != 0) return -1;
        vector<int> prefix(n + 1);
        for (int i = 1; i <= n; ++i) {
            prefix[i] = prefix[i - 1] + stones[i - 1];
        }
        vector<vector<vector<int>>> f(n, vector<vector<int>>(n, vector<int>(K + 1, 0x3f3f3f3f)));
        for (int i = 0; i < n; ++i) {
            f[i][i][1] = 0;
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                for (int k = 2; k <= K; ++k) {
                    for (int m = i; m < j; m += K - 1) {
                        f[i][j][k] = min(f[i][j][k], f[i][m][1] + f[m + 1][j][k - 1]);
                    }
                }
                f[i][j][1] = f[i][j][K] + prefix[j + 1] - prefix[i];
            }
        }
        return f[0][n - 1][1];
    }
};

class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        int n = stones.size();
        if ((n - 1) % (K - 1) != 0) return -1;
        vector<int> prefix(n + 1);
        for (int i = 1; i <= n; ++i) {
            prefix[i] = prefix[i - 1] + stones[i - 1];
        }
        vector<vector<int>> f(n, vector<int>(n, 0x3f3f3f3f));
        for (int i = 0; i < n; ++i) {
            f[i][i] = 0;
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                for (int m = i; m < j; m += K - 1) {
                    f[i][j] = min(f[i][j], f[i][m] + f[m + 1][j]);
                }
                if ((len - 1) % (K - 1) == 0) {
                    f[i][j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return f[0][n - 1];
    }
};

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

动态规划三