动态规划的优化
引入
给定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等技术内容，立即学习
