leetcode算法之动态规划（四 股票问题）
今天来盘一盘 **动态规划 ** 这类题目
这是最让我头疼的一类题目，一直不想做这类题目，这里开始学习一下。
使用python刷题分类整理的笔记,请参考: //github.com/lxztju/leetcode-algorithm/tree/v1
动态规划
动规就是以空间换取时间。
动态规划常常适用于有重叠子问题和最优子结构性质的问题。
一些思考的套路： 递归 （自顶向下）——> 记忆化递归（自顶向下消除重复） ——> 动态规划（自底而上）
-
股票交易
-
121 买卖股票的最佳时机（easy）
-
122 买卖股票的最佳时机II（easy）
-
123 买卖股票的最佳时机 III（hard）
-
188 买卖股票的最佳时机 IV（hard）
-
309 最佳买卖股票时机含冷冻期（medium）
-
714 买卖股票的最佳时机含手续费（medium）
股票交易
对于这类股票交易的问题，可以使用一个同意的模板来解决这类问题。
- 状态方程为：
状态转移方程：
状态方程中的 i 表示第i天， k表示剩余的操作次数(这里以购买作为操作次数的记录）， 0表示不持有股票，1表示持有股票
再第i天不持有股票， 那么其最大利润为上一天不持有股票与上一天持有股票卖掉二者的最大值
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
在第i天持有股票，那么其最大利润为上一天持有股票与上一天不持有股票，然后重新购买二者的最大值
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
- 边界条件：
base case：
#时间从第一天开始
dp[0][k][0] = 0
dp[0][k][1] = -prices[0]
# k为0表示不允许交易
dp[i][0][0] = 0
dp[i][0][1] = -infinity
当然利用这种方法进行处理并不一定是最优的，有时候会存在大量的冗余， 这里主要引入这种统一的解决思路
121 买卖股票的最佳时机（easy）
class Solution {
public:
int maxProfit(vector<int>& prices) {
// 这里只能交易一次，因此k为1， 这里就只需要定义二维数组
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i=1; i< n; i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
// 这里由于只能交易1次。dp[i][0][0] = 0;
dp[i][1] = max(dp[i-1][1], -prices[i]);
}
return dp[n-1][0];
}
};
122 买卖股票的最佳时机II（easy）
class Solution {
public:
int maxProfit(vector<int>& prices) {
// 这里可以交易无数次，因此k不做限制， 这里就只需要定义二维数组
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i=1; i< n; 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]);
}
return dp[n-1][0];
}
};
123 买卖股票的最佳时机 III（hard）
class Solution {
public:
int maxProfit(vector<int>& prices) {
// 这里最多能够完成两笔交易，因此k = 2，需要定义三维数组
int n = prices.size();
vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2, 0)));
for ( int k = 0; k < 3; k++){
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
}
for (int i = 0; i < n; i++){
dp[i][0][0] = 0;
dp[i][0][1] = -INT_MAX;
}
for ( int i = 1; i< n; i++){
for (int k = 1; k <3; k++){
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
return dp[n-1][2][0];
}
};
188 买卖股票的最佳时机 IV（hard）
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
// 这里最多能够完成k笔交易，需要定义三维数组
int n = prices.size();
if (n ==0 || k == 0) return 0;
vector<vector<vector<int>>> dp(n, vector<vector<int>>(k+1, vector<int>(2, 0)));
for ( int k1 = 0; k1 < k+1; k1++){
dp[0][k1][0] = 0;
dp[0][k1][1] = -prices[0];
}
for (int i = 0; i < n; i++){
dp[i][0][0] = 0;
dp[i][0][1] = -INT_MAX;
}
for ( int i = 1; i< n; i++){
for (int k1 = 1; k1 <k+1; k1++){
dp[i][k1][0] = max(dp[i-1][k1][0], dp[i-1][k1][1] + prices[i]);
dp[i][k1][1] = max(dp[i-1][k1][1], dp[i-1][k1-1][0] - prices[i]);
}
}
return dp[n-1][k][0];
}
};
309 最佳买卖股票时机含冷冻期（medium）
class Solution {
public:
int maxProfit(vector<int>& prices) {
// 可以实现无数次的交易，定义二维数组作为dp
int n = prices.size();
if ( n == 0 ) return 0;
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
if (n == 1 ) return 0;
dp[1][0] = max(0, prices[1] - prices[0]);
dp[1][1] = max(-prices[0], -prices[1]);
for (int i = 2; i < n; i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
// 下次购买的时候只能在i-2天不持有的情况下购买
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]);
}
return dp[n-1][0];
}
};
714 买卖股票的最佳时机含手续费（medium）
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
// 这里可以交易无数次，因此k不做限制， 这里就只需要定义二维数组
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i=1; i< n; i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
}
return dp[n-1][0];
}
};
更多分类刷题资料
-
微信公众号： 小哲AI
-
GitHub地址： //github.com/lxztju/leetcode-algorithm
-
csdn博客： //blog.csdn.net/lxztju
-
AI研习社专栏：//www.yanxishe.com/column/109
