class Solution {
public:
int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
int ans = -1e9;
deque<int> q;
for (int i = 0; i < points.size(); i++) {
// while x[j] < x[i] - k, 刪除過期的j
while (!q.empty() && points[q.front()][0] < points[i][0] - k)
q.pop_front();
// ans = max(ans, y[i] + x[i] + y[j] - x[j])
if (!q.empty())
ans = max(ans, points[i][1] + points[i][0] + points[q.front()][1] - points[q.front()][0]);
// y[j]-x[j]遞減的隊列。且因為i不是候選項，所以先維護單調隊列底瓣，再入隊i
while (!q.empty() && points[q.back()][1] - points[q.back()][0] <= points[i][1] - points[i][0])
q.pop_back();
q.push_back(i);
}
return ans;
}
};
/*
yi + yj + |xi - xj| max
假設j<i哮内，則為 yi + yj + xi - xj max
固定i硬毕，則為 yj - xj max
且 |xi - xj| <= k
已假設j<i，則滿足 xi - xj <= k
綜上，題目化為————
求 “yj - xj 在 j 滿足 j < i 且 xj >= xi - k 條件下最大值”
*/
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
// 處理環(huán)形，可以復制一份接在后面都毒，成為2n的數(shù)組
// [1...n][n+1...2n]
int n = nums.size();
nums.insert(nums.begin(), 0);
vector<int> preSum(2 * n + 1, 0);
preSum[0] = 0;
for (int i = 1; i <= n; i++)
preSum[i] = preSum[i - 1] + nums[i];
for (int i = n + 1; i <= 2 * n; i++)
preSum[i] = preSum[i - 1] + nums[i - n];
int ans = -1e9;
deque<int> q;
for (int i = 1; i <= 2 * n; i++) {
// j 的范圍 [i-n, i-1]
// 當 j < i - n 刪除
while (!q.empty() && q.front() < i - n)
q.pop_front();
if (!q.empty())
ans = max(ans, preSum[i] - preSum[q.front()]);
while (!q.empty() && preSum[q.back()] >= preSum[i])
q.pop_back();
q.push_back(i);
}
return ans;
}
};
-
312. 戳氣球 - 力扣（LeetCode）
法一：區(qū)間DP
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));
for (int len = 1; len <= n; len++) // 區(qū)間動態(tài)規(guī)劃，最外層循環(huán)其區(qū)間長度
for (int l = 1; l <= n - len + 1; l++) { // 然后循環(huán)左端點
int r = l + len - 1; // 計算出右端點
for (int p = l; p <= r; p++)
f[l][r] = max(f[l][r], f[l][p - 1] + f[p + 1][r] + nums[p] * nums[l - 1] * nums[r + 1]);
}
return f[1][n];
}
};
法二：遞歸+記憶化
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
this->nums = nums;
f = vector<vector<int>>(n + 2, vector<int>(n + 2, -1));
return calc(1, n);
}
private:
vector<int> nums;
vector<vector<int>> f;
int calc(int l, int r) {
if (l > r) return 0;
if (f[l][r] != -1) return f[l][r];
for (int p = l; p <= r; p++)
f[l][r] = max(f[l][r], calc(l, p - 1) + calc(p + 1, r) + nums[p] * nums[l - 1] * nums[r + 1]);
return f[l][r];
}
};
-
1000. 合并石頭的最低成本 - 力扣（LeetCode）
區(qū)間DP
class Solution {
public:
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
vector<vector<vector<int>>> f(n, vector<vector<int>>(n, vector<int>(k + 1, 1e9)));
for (int i = 0; i < n; i++) f[i][i][1] = 0;
for (int len = 2; len <= n; len++)
for (int l = 0; l < n - len + 1; l++) {
int r = l + len - 1;
for (int i = 2; i <= k; i++)
for (int p = l; p < r; p++)
f[l][r][i] = min(f[l][r][i], f[l][p][1] + f[p + 1][r][i - 1]);
int sum = 0;
for (int i = l; i <= r; i++) sum += stones[i];
f[l][r][1] = min(f[l][r][1], f[l][r][k] + sum);
}
return f[0][n - 1][1] == 1e9 ? -1 : f[0][n - 1][1];
}
};
-
337. 打家劫舍 III - 力扣（LeetCode）
樹狀動規(guī)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
f.insert({nullptr, {0, 0}});
dfs(root);
return max(f[root][1], f[root][0]);
}
private:
unordered_map<TreeNode*, vector<int>> f;
void dfs(TreeNode* root) {
if (root == nullptr) return;
dfs(root->left);
dfs(root->right);
f.insert({root, {0, 0}});
f[root][0] = max(f[root->left][0], f[root->left][1]) + max(f[root->right][0], f[root->right][1]);
f[root][1] = f[root->left][0] + f[root->right][0] + root->val;
}
};
class Solution {
public:
int numSquares(int n) {
vector<int> f(n + 1, 1e9);
f[0] = 0;
for (int i = 1; i * i <= n; i++)
for (int j = i * i; j <= n; j++)
f[j] = min(f[j], f[j - i * i] + 1);
return f[n];
}
};
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int farthest = 0;
for (int i = 0; i < n; i++)
if (i <= farthest) {
farthest = max(farthest, i + nums[i]);
if (farthest >= n - 1) return true;
}
return false;
}
};
