class Solution {
public:
int minimumEffort(vector<vector<int>>& tasks) {
sort(tasks.begin(), tasks.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] - a[1] < b[0] - b[1];
});
int ans = 0;
for (int i = tasks.size() - 1; i >= 0; i--)
ans = max(tasks[i][1], ans + tasks[i][0]);
return ans;
}
/*
考虑任意一种做任务的顺序，设做完第i+2到n个任务所需的初始能量最少为S
对于两个相邻任务：设第i个和第i+1个完成的任务分别是p和q
·先做p，所需初始能量为：max(max(min[q], S+actual[q])+actual[p], min[p]);
·先做q，所需初始能量为：max(max(min[p], S+actual[p])+actual[q], min[q]);
假设先做p比较优，则应该满足
max(max(min[q], S+actual[q])+actual[p], min[p])
< max(max(min[p], S+actual[p])+actual[q], min[q])
两边消去相同式子
max(min[q]+actual[p], min[p]) < max(min[p]+actual[q], min[q])
又因为min[q]+actual[p] > min[q]
所以不等式等价于min[q]+actual[p] < min[p]+actual[q]
即actual[p] - min[p] < actual[q] - min[q]，其中p<q
则原题目中，要求最小，则按照actual-min升序排列，即可。
*/
};
-
63. 不同路径 II - 力扣（LeetCode）
法一：记忆化搜索-递归
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
m = obstacleGrid.size();
n = obstacleGrid[0].size();
grid = obstacleGrid;
return countPaths(0, 0);
}
private:
int m, n;
vector<vector<int>> grid;
map<pair<int, int>, int> dic;
int countPaths(int row, int col) {
if (dic.find({row, col}) != dic.end()) return dic[{row, col}];
if (row >= m || col >= n || grid[row][col] == 1) return 0;
if (row == m - 1 && col == n - 1) return dic[{row, col}] = 1;
return dic[{row, col}] = countPaths(row + 1, col) + countPaths(row, col + 1);
}
};
法二：DP
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> f(m, vector<int>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (obstacleGrid[i][j] == 1) f[i][j] = 0;
else if (i == 0 && j == 0) f[i][j] = 1;
else if (i == 0) f[i][j] = f[i][j - 1];
else if (j == 0) f[i][j] = f[i - 1][j];
else f[i][j] = f[i - 1][j] + f[i][j - 1];
return f[m - 1][n - 1];
}
};
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length(), n = text2.length();
text1 = " " + text1;
text2 = " " + text2;
vector<vector<int>> f(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (text1[i] == text2[j])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
return f[m][n];
}
};
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> f(n, 1); // !!! 初始以每个成员为结尾的最长递增子序列为1
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (nums[j] < nums[i])
f[i] = max(f[i], f[j] + 1);
int ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, f[i]);
return ans;
}
};
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
f[0] = nums[0];
for (int i = 1; i < n; i++)
f[i] = max(f[i - 1] + nums[i], nums[i]);
int ans = f[0];
for (int i = 1; i < n; i++)
ans = max(ans, f[i]);
return ans;
}
};
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> fmax(n);
vector<int> fmin(n);
fmax[0] = fmin[0] = nums[0];
for (int i = 1; i < n; i++) {
fmax[i] = max(max(fmax[i - 1] * nums[i], fmin[i - 1] * nums[i]), nums[i]);
fmin[i] = min(min(fmax[i - 1] * nums[i], fmin[i - 1] * nums[i]), nums[i]);
}
int ans = nums[0];
for (int i = 1; i < n; i++)
ans = max(ans, fmax[i]);
return ans;
}
};
class Solution {
public:
int climbStairs(int n) {
vector<int> f(n + 1);
f[0] = 1, f[1] = 1;
for (int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
return f[n];
}
};
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
int tot = (1 + n) * n / 2;
vector<int> f(tot);
f[0] = triangle[0][0];
for (int i = 1; i < n; i++) {
f[pos(i, 0)] = f[pos(i - 1, 0)] + triangle[i][0];
f[pos(i, i)] = f[pos(i - 1, i - 1)] + triangle[i][i];
for (int j = 1; j < i; j++)
f[pos(i, j)] = min(f[pos(i - 1, j - 1)], f[pos(i - 1, j)]) + triangle[i][j];
}
int ans = f[tot - n];
for (int i = tot - n; i < tot; i++)
ans = min(ans, f[i]);
return ans;
}
private:
int pos(int i, int j) {
return (1 + i) * i / 2 + j;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<int> preMin(n + 1, 1e5);
for (int i = 1; i <= n; i++)
preMin[i] = min(preMin[i - 1], prices[i - 1]);
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, prices[i - 1] - preMin[i]);
return ans;
}
};
/* [7,1,5,3,6,4]
n = 6
prices=[ 7,1,5,3,6,4]
preMin=[0,7,1,1,1,1,1]
*/
10.9. 回文数 - 力扣（LeetCode）
O(∩_∩)O小插曲
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0 || (x != 0 && x % 10 == 0)) return false;
int reverse = 0;
while (x > reverse) {
reverse = reverse * 10 + x % 10;
x /= 10;
}
return reverse == x || reverse / 10 == x;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
// 0. Move index to 1-based
prices.insert(prices.begin(), 0);
// 1. Define f, initialize -oo
vector<vector<int>> f(n + 1, vector<int>(2, -1e9));
f[0][0] = 0;
// 2. Loop over all states
for (int i = 1; i <= n; i++) {
// 3. Copy decisions
f[i][1] = max(f[i][1], f[i - 1][0] - prices[i]);
f[i][0] = max(f[i][0], f[i - 1][1] + prices[i]);
for (int j = 0; j < 2; j++)
f[i][j] = max(f[i][j], f[i - 1][j]);
}
// 4. Return target
return f[n][0];
}
};
class Solution {
public:
int maxProfit(int c, vector<int>& prices) {
int n = prices.size();
// 0. Move index to 1-based
prices.insert(prices.begin(), 0);
// 1. Define f, initialize -oo
vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(2
, vector<int>(c + 1, -1e9)));
f[0][0][0] = 0;
// 2. Loop over all states
for (int i = 1; i <= n; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k <= c; k++) {
// 3. Copy decision funcs
if (k > 0) f[i][0][k] = max(f[i][0][k], f[i - 1][1][k - 1] + prices[i]);
f[i][1][k] = max(f[i][1][k], f[i - 1][0][k] - prices[i]);
f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]);
}
// 4. Return target
int ans = -1e9;
for (int k = 0; k <= c; k++)
ans = max(ans, f[n][0][k]);
return ans;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
// 0. Move index to 1-based
prices.insert(prices.begin(), 0);
// 1. Define f, initialize -oo
vector<vector<int>> f(n + 1, vector<int>(2, -1e9));
f[0][0] = 0;
// 2. Loop over all states
for (int i = 1; i <= n; i++) {
f[i][1] = max(f[i][1], f[i - 1][0] - prices[i] - fee);
f[i][0] = max(f[i][0], f[i - 1][1] + prices[i]);
for (int j = 0; j < 2; j++)
f[i][j] = max(f[i][j], f[i - 1][j]);
}
return f[n][0];
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
// 0. Move index to 1-based
prices.insert(prices.begin(), 0);
// 1. Define f, initialize -oo
vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(2,
vector<int>(2, -1e9)));
f[0][0][0] = 0;
// 2. Loop over all states
for (int i = 1; i <= n; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++) {
// 3. Copy decision funcs
f[i][1][0] = max(f[i][1][0], f[i - 1][0][0] - prices[i]);
f[i][0][1] = max(f[i][0][1], f[i - 1][1][0] + prices[i]);
f[i][j][0] = max(f[i][j][0], f[i - 1][j][k]);
}
// 4. Return target
return max(f[n][0][0], f[n][0][1]);
}
};
