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
