买卖股票的最佳时机(简单)
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。买卖股票的最佳时机
思路：总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。我们要穷举所有「状态」，穷举的目的是根据对应的「选择」更新状态。股票买卖的状态有3个，第一个是天数、第二个是允许交易的最大次数、第三个是当前持有的状态。每天都有三种选择：买入、卖出、无操作。
状态表示：dp[i][j][0]: 表示所有经过了i天，已经进行了j场交易，且手中未持有股票的所有集合，dp[i][j][1]：表示所有经过了i填，已经进行了j-1次交易，且手中持有股票进行第j次交易的所有集合，其属性是：最大收益。
状态计算：dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + w[i]),dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] -w[i]);
团灭LeetCode股票买卖问题
动态规划
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
// 解释：今天没有持有股票，有两种可能：(1)前一天没有持有;(2)前一天持有，今天卖出，所有今天就没有持有股票了
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1] - prices[i]);
// 解释：今天持有股票，有两种可能：(1)前一天持有；(2)前一天没有持有，今天买入，所以今天就持有股票了
// base case
dp[i][0][0] = 0;
// i = 0时，dp[i][j][0] = max(dp[-1][j][0], dp[-1][j][1] + prices[i]) = max(0, -INF + prices[i]) = 0;
// 解释：dp[-1][j][0] = 0：i是从1开始的，i=-1表示交易还没开始，利润为0；dp[-1][j][1] = -INF：表示还没开始时是不可能持有股票的，用负无穷表示这种状态。
dp[i][0][1] = -INF;
// k = 0时，dp[i][k][1] = max(dp[-1][k][1], dp[-1][k-1][0] - prices[i]) = max(-INF, -prices[i]) = -prices
// 解释：dp[i][0][0] = 0：因为k是从1开始的，k=0说明没有交易，利润为0；dp[i][0][1] = -INF：没有交易的情况下是不可能持有股票的。
// 状态转移方程
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
// 代码 未优化版本
int maxProfit(vector<int>& prices) {
if (!prices.size()) return 0;
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2));
for (int i = 0; i < n; i++) {
if (!i) {
dp[i][0] = 0; // 解释： dp[i][0] = max(dp[-1][0], dp[-1][1] + prices[i]) = max(0, -INF + prices[i]) = 0;
dp[i][1] = -prices[i]; // 解释：dp[i][1] = max(dp[-1][1], dp[-1][0] - prices[i]) = max(-INF, -prices[i]) = -prices[i];
} else {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], -prices[i]);
}
}
return dp[n-1][0];
}
// 优化版本
int maxProfit(vector<int>& prices) {
if (!prices.size()) return 0;
int dp_i_0 = 0, dp_i_1 = INT_MIN;
for (int i = 0; i < prices.size(); i++) {
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = max(dp_i_1, -prices[i]);
}
return dp_i_0;
}
买卖股票的最佳时机II(简单)
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。买卖股票的最佳时机II
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
// 和交易次数无关，可以把交易次数去掉
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
// 未优化版本
int maxProfit(vector<int>& prices) {
if (!prices.size()) return 0;
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2));
for (int i = 0; i < n; i++) {
if (!i) {
dp[i][0] = 0;
dp[i][1] = -prices[i];
} else {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
}
}
return dp[n-1][0];
}
// 优化版本
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (!n) return 0;
int dp_i_0 = 0, dp_i_1 = INT_MIN;
for (int i = 0; i < prices.size(); i++) {
int t = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = max(dp_i_1, t - prices[i]);
}
return dp_i_0;
}
买卖股票的最佳时机III(困难)
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。买卖股票的最佳时机III
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
// 未优化版本
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (!n) return 0;
vector<vector<vector<int>>> dp(n, vector<vector<int>>(2 + 1, vector<int>(2)));
for (int i = 0; i < prices.size(); i++) {
dp[i][0][0] = 0;
dp[i][0][1] = INT_MIN;
for(int j = 2; j >= 1; j--) { // 需要枚举交易次数
if (!i) { // base case
dp[i][j][0] = 0;
dp[i][j][1] = -prices[i];
} else {
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
}
}
}
return dp[n-1][2][0];
}
// 优化版本
// 枚举状态转移方程
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i])
int maxProfit(vector<int>& prices) {
int dp_i_1_0 = 0, dp_i_1_1 = INT_MIN, dp_i_2_0 = 0, dp_i_2_1 = INT_MIN;
for (auto p : prices) {
dp_i_2_0 = max(dp_i_2_0, dp_i_2_1 + p);
dp_i_2_1 = max(dp_i_2_1, dp_i_1_0 - p);
dp_i_1_0 = max(dp_i_1_0, dp_i_1_1 + p);
dp_i_1_1 = max(dp_i_1_1, -p);
}
return dp_i_2_0;
}
买卖股票的最佳时机IV(困难)
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。买卖股票的最佳时机IV
思路：有了上一题 k = 2 的铺垫，这题应该和上一题的第一个解法没啥区别。但是出现了一个超内存的错误，原来是传入的 k 值会非常大，dp 数组太大了。现在想想，交易次数 k 最多有多大呢？一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (k > n / 2) return maxProfitKInf(prices); // 这种情况就和k没有关系了
vector<vector<vector<int>>> dp(n, vector<vector<int>>(k + 1, vector<int>(2)));
for (int i = 0; i < n; i++) {
dp[i][0][0] = 0;
dp[i][0][1] = INT_MIN;
for (int j = k; j > 0; j--) {
if (!i) {
dp[i][j][0] = 0;
dp[i][j][1] = -prices[i];
} else {
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
}
}
}
return dp[n-1][k][0];
}
int maxProfitKInf(vector<int>& prices) {
int n = prices.size();
if (!n) return 0;
int dp_i_0 = 0, dp_i_1 = INT_MIN;
for (auto p : prices) {
int t = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + p);
dp_i_1 = max(dp_i_1, t - p);
}
return dp_i_0;
}
买卖股票的最佳时机含冷冻期(中等)
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。买卖股票的最佳时机含冷冻期
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]);
// 解释：第i天选择买的时候，要从i-2的状态转移，而不是i-1。
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (!n) return 0;
vector<vector<int>> dp(n, vector<int>(2));
for(int i = 0; i < prices.size(); i++) {
// 不会写了。。。
}
}
// 优化版本
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (!n) return 0;
int dp_i_0 = 0, dp_i_1 = INT_MIN;
int dp_pre_0 = 0;
for (auto p : prices) {
int t = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = t;
}
return dp_i_0;
}
买卖股票的最佳时机含手续费(中等)
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。买卖股票的最佳时机含手续费
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
// 解释：相当于在买入股票的时候价格升高了
// 未优化版本
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
if (!n) return 0;
vector<vector<int>> dp(n, vector<int>(2));
for (int i = 0; i < n; i++) {
if (!i) {
dp[i][0] = 0;
dp[i][1] = -prices[i] - fee;
} else {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee);
}
}
return dp[n-1][0];
}
// 优化版本
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
if (!n) return 0;
int dp_i_0 = 0, dp_i_1 = INT_MIN;
for (auto p : prices) {
int t = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + p);
dp_i_1 = max(dp_i_1, t - p - fee);
}
return dp_i_0;
}
打家劫舍(简单)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。打家劫舍
思路：状态表示：dp[i]表示从前i家偷的所有合法方案，其值是最大收益。状态计算：dp[i] = max(dp[i-1], dp[i-2] + w[i])，当前位置不抢和当前位置抢里面的最大值。
团灭LeetCode打家劫舍问题
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int rob(vector<int>& nums) {
int n = nums.size();
if (!n) return 0;
vector<int> dp(n + 1);
dp[0] = 0, dp[1] = nums[0];
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[n];
}
// 空间优化
int rob(vector<int>& nums) {
int n = nums.size();
if (!n) return 0;
int dp_i_1 = 0, dp_i_2 = 0;
int dp_i = 0;
for (auto n : nums) {
dp_i = max(dp_i_1, dp_i_2 + n);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}
打家劫舍II(中等)
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。打家劫舍II
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int rob(vector<int>& nums) {
int n = nums.size();
if (!n) return 0;
if (n == 1) return nums[0];
return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
int robRange(vector<int>& nums, int b, int e) {
int dp_i_1 = 0, dp_i_2 = 0;
int dp_i = 0;
for (int i = b; i <= e; i++) {
dp_i = max(dp_i_1, dp_i_2 + nums[i]);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}
打家劫舍III(中等)
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。打家劫舍III
参考代码
1
2
3
4
5
6
7
8
9
10
unordered_map<TreeNode*, int> memo;
int rob(TreeNode* root) {
if (!root) return 0;
if (memo.count(root)) return memo[root];
int do_it = root->val + (!root->left ? 0 : rob(root->left->left) + rob(root->left->right)) + (!root->right ? 0 : rob(root->right->left) + rob(root->right->right));
int not_do = rob(root->left) + rob(root->right);
int res = max(do_it, not_do);
memo[root] = res;
return res;
}
KMP字符串匹配
字符串匹配
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
int search(string s, string p) {
int M = p.size(), N = s.size();
// 动态数组 dp[状态][字符] = 下一个状态
vector<vector<int>> dp(M, vector<int>(256, 0));
// base case
dp[0][p[0]] = 1;
// 影子状态初始化为0
int X = 0;
// 利用模式串构建状态转移图
for (int j = 1; j < M; j++) {
for (int c = 0; c < 256; c++) {
if (p[j] == c)
dp[j][c] = j + 1;
else
dp[j][c] = dp[X][c];
}
X = dp[X][p[j]];
}
int j = 0; // 记录状态 模式初始状态为0
// 在字符串中匹配
for (int i = 0; i < N; i++) {
j = dp[j][s[i]];
// 如果状态到达模式串尾部，说明匹配成功
if (j == M) return i - M + 1;
}
return -1;
}
int main() {
string s, p;
while (cin >> s >> p) {
cout << search(s, p) << endl;
}
return 0;
}
