动态规划中优化枚举（上）
动态规划中优化枚举减少状态转移复杂度，通过单调性、二分、单调队列等技巧加速计算，提高效率。
动态规划中优化枚举（上）
动态规划中优化枚举
121. 买卖股票的最佳时机
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int res = 0;
// 0~i 上最小值
int m = prices[0];
for (int i = 1; i < prices.size(); ++i) {
m = min(m, prices[i]);
res = max(res, prices[i] - m);
}
return res;
}
};
122. 买卖股票的最佳时机 II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int res = 0;
for (int i = 1; i < prices.size(); ++i)
res += max(prices[i] - prices[i - 1], 0);
return res;
}
};
123. 买卖股票的最佳时机 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
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n = prices.size();
// dp1[i]: 在 0~i 范围发生一次交易能得到的最大利润，不要求一定要在 i 时卖出
vector<int> dp1(n);
for (int i = 1, m = prices[0]; i < n; ++i) {
m = min(m, prices[i]);
// p1: 不在 i 时卖出，dp1[i - 1]
// p2: 在 i 时卖出，prices[i] - m
dp1[i] = max(dp1[i - 1], prices[i] - m);
}
// dp2[i]: 在 0~i 范围发生两次交易能得到的最大利润，要求第二次交易在 i 时卖出
vector<int> dp2(n);
int res = 0;
// 第二次交易一定要在 i 时卖出
for (int i = 1; i < n; ++i) {
// 枚举第二次交易买入时间 j
for (int j = 0; j <= i; ++j)
dp2[i] = max(dp2[i], dp1[j] + prices[i] - prices[j]);
res = max(res, dp2[i]);
}
return res;
}
};
- 优化 for 循环
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
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n = prices.size();
// dp1[i]: 在 0~i 范围发生一次交易能得到的最大利润，不要求一定要在 i 时卖出
vector<int> dp1(n, 0);
for (int i = 1, m = prices[0]; i < n; ++i) {
m = min(m, prices[i]);
// p1: 不在 i 时卖出，dp1[i - 1]
// p2: 在 i 时卖出，prices[i] - m
dp1[i] = max(dp1[i - 1], prices[i] - m);
}
// best[i]: 0~i 范围，所有的 dp1[i] - prices[i] 的最大值
vector<int> best(n);
best[0] = dp1[0] - prices[0];
for (int i = 1; i < n; ++i) {
best[i] = max(best[i - 1], dp1[i] - prices[i]);
}
// dp2[i]: 在 0~i 范围发生两次交易能得到的最大利润，要求第二次交易在 i 时卖出
vector<int> dp2(n);
int res = 0;
// 第二次交易一定要在 i 时卖出
for (int i = 1; i < n; ++i) {
// 省去枚举
dp2[i] = best[i] + prices[i];
res = max(res, dp2[i]);
}
return res;
}
};
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
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n = prices.size();
vector<int> dp1(n, 0);
vector<int> best(n);
best[0] = dp1[0] - prices[0];
vector<int> dp2(n);
int res = 0;
for (int i = 1, m = prices[0]; i < n; ++i) {
m = min(m, prices[i]);
dp1[i] = max(dp1[i - 1], prices[i] - m);
best[i] = max(best[i - 1], dp1[i] - prices[i]);
dp2[i] = best[i] + prices[i];
res = max(res, dp2[i]);
}
return res;
}
};
- 空间压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n = prices.size();
int dp1 = 0;
int best = dp1 - prices[0];
int res = 0;
for (int i = 1, m = prices[0]; i < n; ++i) {
m = min(m, prices[i]);
dp1 = max(dp1, prices[i] - m);
best = max(best, dp1 - prices[i]);
res = max(res, best + prices[i]);
}
return res;
}
};
188. 买卖股票的最佳时机 IV
- 暴力 DP，时间复杂度为 O(k * n²)
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// 股票问题 2 的解法
int free(const vector<int> &prices) {
int res = 0;
for (size_t i = 1; i < prices.size(); ++i)
res += max(prices[i] - prices[i - 1], 0);
return res;
}
int maxProfit(int k, const vector<int> &prices) {
int n = prices.size();
// 由于一次完整的交易（买+卖）至少需要两天，因此最多能交易 n/2 次
// 当交易次数允许大于 n/2 时，问题等价于股票问题 2
if (k >= n / 2) return free(prices);
// 第一行第一列都是 0
// dp[i][j]: 在 0~j 天进行 i 次交易能获得的最大利润
vector<vector<int>> dp(k + 1, vector<int>(n, 0));
for (int i = 1; i <= k; ++i) {
for (int j = 1; j < n; ++j) {
// p1: 最后一笔交易不是在第 j 天卖出
dp[i][j] = dp[i][j - 1];
// p2: 枚举第 j 天卖出，看看买入时间是哪一天最优
for (int p = 0; p < j; ++p) {
// 第 i 次交易的利润 = 第 i-1 次交易在第 p 天之前的利润 + 第 p 天买入第 j 天卖出的利润
dp[i][j] = max(dp[i][j], dp[i - 1][p] + prices[j] - prices[p]);
}
}
}
return dp[k][n - 1];
}
};
- 优化版，时间复杂度 O(k * n)
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int free(const vector<int> &prices) {
int res = 0;
for (size_t i = 1; i < prices.size(); ++i)
res += max(prices[i] - prices[i - 1], 0);
return res;
}
// 股票问题 4：最多进行 k 次交易的最大利润（优化版，时间复杂度 O(k * n)）
int maxProfit(int k, const vector<int> &prices) {
int n = prices.size();
if (k >= n / 2) return free(prices);
// dp[i][j]: 在 0~j 天进行 i 次交易能获得的最大利润
vector<vector<int>> dp(k + 1, vector<int>(n, 0));
// 枚举交易次数（从 1 到 k）
for (int i = 1; i <= k; ++i) {
// best 表示在第 j 天买入时，前面状态能获得的最大利润
// best = max(dp[i - 1][m] - prices[m])，其中 m < j
int best = dp[i - 1][0] - prices[0];
// 枚举天数（从第 1 天开始）
for (int j = 1; j < n; ++j) {
// 不进行交易：延续前一天的利润
// 进行交易：前一次交易的最大利润 + 今天卖出
dp[i][j] = max(dp[i][j - 1], best + prices[j]);
// 更新 best，表示未来某天买入时参考的最大基准
best = max(best, dp[i - 1][j] - prices[j]);
}
}
return dp[k][n - 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int free(const vector<int> &prices) {
int res = 0;
for (size_t i = 1; i < prices.size(); ++i)
res += max(prices[i] - prices[i - 1], 0);
return res;
}
int maxProfit(int k, const vector<int> &prices) {
int n = prices.size();
if (k >= n / 2) return free(prices);
vector<int> dp(n, 0);
// 外层枚举交易次数（从 1 到 k）
for (int i = 1; i <= k; ++i) {
int best = dp[0] - prices[0]; // 表示在当前轮中，第 0 天买入时的最优状态
for (int j = 1, tmp; j < n; ++j) {
tmp = dp[j]; // 先保存当前 dp[j]（上一轮的状态），用于后续更新 best
// 更新当前交易次数下，第 j 天结束时的最大利润
// 两种选择：
// 1. 不交易：保持前一天的利润 dp[j - 1]
// 2. 卖出：使用 best + prices[j]
dp[j] = max(dp[j - 1], best + prices[j]);
// 更新 best（相当于模拟前面某天买入的最优状态）
// 即 dp[i - 1][j] - prices[j]，但用了滚动数组，只能通过 tmp 保留旧值
best = max(best, tmp - prices[j]);
}
}
return dp[n - 1];
}
};
714. 买卖股票的最佳时机含手续费
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// fee: 每笔交易的手续费
int maxProfit(const vector<int> &prices, int fee) {
// prepare：当前持有一支股票的状态（扣掉了买入成本和手续费）
// 初始化为第 0 天买入一支股票后，净利润为 -prices[0] - fee
int prepare = -prices[0] - fee;
// done：当前没有持股的状态，表示卖出后处于空仓状态时的最大利润
int done = 0;
// 从第 1 天开始模拟每天的买入或卖出行为
for (int i = 1; i < prices.size(); ++i) {
// p1: 第 i 天不交易
// P2: 第 i 天卖出，昨天持有股票状态 + 今天价格，尝试更新空仓最大收益
done = max(done, prepare + prices[i]);
// p1: 不在第 i 天买入
// p2: 在第 i 天买入
prepare = max(prepare, done - prices[i] - fee);
}
return done;
}
};
309. 买卖股票的最佳时机含冷冻期
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProfit(const vector<int> &prices) {
int n = prices.size();
if (n < 2) return 0;
// prepare[i] 表示第 i 天持有股票的最大利润（扣掉买入成本）
vector<int> prepare(n, 0);
// done[i] 表示第 i 天未持股的最大利润
vector<int> done(n, 0);
// 第一天只能买，第二天最多买一次或卖一次
prepare[1] = max(-prices[0], -prices[1]);
done[1] = max(0, prices[1] - prices[0]);
for (int i = 2; i < n; ++i) {
// 当前未持股状态的最大收益 = 昨天不操作 or 昨天持股今天卖出
done[i] = max(done[i - 1], prepare[i - 1] + prices[i]);
// 当前持股状态的最大收益 = 昨天持股 or 前天卖出后今天买入（冷冻期）
prepare[i] = max(prepare[i - 1], done[i - 2] - prices[i]);
}
return done[n - 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
27
28
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// 方法2：空间压缩，只保留最近两天的状态
int maxProfit(const vector<int> &prices) {
int n = prices.size();
if (n < 2) return 0;
// 初始化
int prepare = max(-prices[0], -prices[1]); // 第 1 天持股状态
int done2 = 0; // 第 0 天不持股状态
int done1 = max(0, prices[1] - prices[0]); // 第 1 天不持股状态
for (int i = 2; i < n; ++i) {
int curDone = max(done1, prepare + prices[i]); // 今天不持股：不动 or 卖出
prepare = max(prepare, done2 - prices[i]); // 今天持股：不动 or 买入（冷冻）
done2 = done1; // 滚动更新
done1 = curDone;
}
return done1;
}
};
903. DI 序列的有效排列
- 暴力递归
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
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
static constexpr int MOD = 1e9 + 7;
// 递归尝试：当前在 s 的第 i 位置，i - 1 位置的数字已经确定，i 位置的数字还没确定
// less 表示当前剩下数字中比前一个小的数量
// 比前一个大的数量为 n - i - less
int fc(const string &s, int i, int less, int n) {
if (i == n) return 1;
int res = 0;
if (i == 0 || s[i - 1] == 'D') {
for (int nextLess = 0; nextLess < less; ++nextLess)
res = (res + fc(s, i + 1, nextLess, n)) % MOD;
} else {
for (int nextLess = less, k = 1; k <= n - i - less; ++k, ++nextLess)
res = (res + fc(s, i + 1, nextLess, n)) % MOD;
}
return res;
}
int numPermsDISequence(string s) {
return fc(s, 0, s.length() + 1, s.length() + 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
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
static constexpr int MOD = 1e9 + 7;
int numPermsDISequence(string str) {
int n = str.length() + 1;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int less = 0; less <= n; ++less)
dp[n][less] = 1;
// 从后往前递推
for (int i = n - 1; i >= 0; --i) {
for (int less = 0; less <= n; ++less) {
if (i == 0 || str[i - 1] == 'D') {
for (int nextLess = 0; nextLess < less; ++nextLess)
dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % MOD;
} else {
for (int nextLess = less, k = 1; k <= n - i - less; ++k, ++nextLess)
dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % MOD;
}
}
}
return dp[0][n];
}
};
- 优化枚举
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
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
static constexpr int MOD = 1e9 + 7;
int numPermsDISequence(string str) {
int n = str.length() + 1;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int less = 0; less <= n; ++less)
dp[n][less] = 1;
for (int i = n - 1; i >= 0; --i) {
if (i == 0 || str[i - 1] == 'D') {
dp[i][1] = dp[i + 1][0];
for (int less = 2; less <= n; ++less)
dp[i][less] = (dp[i][less - 1] + dp[i + 1][less - 1]) % MOD;
} else {
dp[i][n - i - 1] = dp[i + 1][n - i - 1];
for (int less = n - i - 2; less >= 0; --less)
dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % MOD;
}
}
return dp[0][n];
}
};
本文由作者按照 CC BY 4.0 进行授权