当前位置：首页 > news >正文

[Algorithm][综合训练][拜访][买卖股票的最好时机(四)]详细讲解

news 来源：原创 2024/9/15 17:20:26

1.拜访

1.题目链接

拜访

2.算法原理详解 && 代码实现

说明：单纯积累一下这种模型 -> 最短路并维护最短路的数量

解法：单源最短路 -> BFS

dist[][]：用于标记最短距离和是否走过该点
cnt[][]：用于记录走到此处为最短距离时的方案个数

class Solution 
{int n, m;int x1, y1, x2, y2;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};vector<vector<int>> dist;vector<vector<int>> cnt;public:int countPath(vector<vector<int>>& CityMap, int _n, int _m) {n = _n, m = _m;dist.resize(n, vector<int>(m, -1));cnt.resize(n, vector<int>(m, 0));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(CityMap[i][j] == 1){x1 = i, y1 = j;}else if(CityMap[i][j] == 2){x2 = i, y2 = j;}}}return BFS(CityMap);}int BFS(vector<vector<int>>& CityMap){queue<pair<int, int>> q;q.push({x1, y1});dist[x1][y1] = 0;cnt[x1][y1] = 1;while(q.size()){auto [a, b] = q.front();q.pop();for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < n && y >= 0 && y < m && CityMap[x][y] != -1){if(dist[x][y] == -1) // 第⼀次到这个位置{dist[x][y] = dist[a][b] + 1;cnt[x][y] = cnt[a][b];q.push({x, y});}else // 不是第一次{if(dist[a][b] + 1 == dist[x][y]) // 是否是最短路{cnt[x][y] += cnt[a][b];}}}}}return cnt[x2][y2];}
};

2.买卖股票的最好时机(四)

1.题目链接

买卖股票的最好时机(四)

2.算法原理详解 && 代码实现

细节：可能k > n / 2，此时开空间时，会多开很多无意义的空间
- 此时k = min(k, n / 2)可以解决该问题

解法：

状态表示：第i天结束之后，所能获得的最大利润
- f[i][j]：第i天结束之后，完成了j次交易，处于“买入”状态，此时的最大利润
- g[i][j]：第i天结束之后，完成了j次交易，处于“卖出”状态，此时的最大利润
状态转移方程：本题关系复杂，可以画图辅助
- f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i])
- g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + p[i])
  - 初始化时，只有g需要特殊处理第一列，而f并不需要
  - 为了避免这种情况，可以将这个状态方程拆成多步，分步执行
    - g[i][j] = g[i - 1][j]
    - if(j - 1 >= 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i])
初始化：
返回值：g[n - 1]中的最大值

#include <iostream>
#include <vector>
using namespace std;const int INF = -0x3f3f3f3f;int main()
{int n = 0, k = 0;cin >> n >> k;k = min(k, n / 2); // 优化处理细节，避免空间浪费vector<int> prices(n, 0);for(auto& x : prices){cin >> x;}vector<vector<int>> f(n, vector<int>(k + 1, INF));vector<vector<int>> g(n, vector<int>(k + 1, INF));f[0][0] = -prices[0], g[0][0] = 0;for(int i = 1; i < n; i++){for(int j = 0; j <= k; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);// 避免越界g[i][j] = g[i - 1][j];if(j - 1 >= 0){g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}}int ret = 0;for(int i = 0; i <= k; i++){ret = max(ret, g[n - 1][i]);}cout << ret << endl;return 0;
}