动态规划三

动态规划三

动态规划三

• 动态规划的优化
• • 引入
  • 第一步优化
  • 第二步优化
  • 第三步优化
  • O(n)代码
  • 动态规划的转移优化思想
  • 进一步思考
  • 1499.满足不等式的最大值
  • 918.环形了数组的最大和
• 区间动态规划
• • 312.戳气球
  • 1000.合并石头的最低成本
• 树形动态规划

动态规划的优化

引入

给定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.满足不等式的最大值

/

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 的第一个索引 iint 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:// 使用二分搜索找到 ] 区间中横坐标 >= 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){ase({points[j][1] - points[j][0], points[j][0]});j ++;}// 使用红黑树最大元素信息更新解if(!pty())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(!pty() && points[i][0] - tree.rbegin()->second > ase(--d());// 使用红黑树最大元素信息更新解if(!pty())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.环形了数组的最大和

/

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.戳气球

/

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();size(n + 2);for (int i = 1; i <= n; i++) {val[i] = nums[i - 1];}val[0] = val[n + 1] = size(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.合并石头的最低成本

/

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];}
};

树形动态规划

=1041943