LeetCode 188. Best Time to Buy and Sell Stock IV (DP with doing nothing)

 188. Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

 

Constraints:

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

	class Solution {
	public:
	/*
	Framework DP (with Doing Nothing)
	1. function
	- states
	i: ith day
	t: remaining transaction
	h: if we are holding stock or not
	- dp[i][t][h]: ith day, t transaction remains, with hold or not = max profit
	- answer
	- dp[0][k][0]
	2. relation
	- (holding) dp[i][t][1] = max(dp[i+1][t][1], dp[i+1][t-1][0] - prices[i])
	- (not holding) dp[i][t][0] = max(dp[i+1][t][0], dp[i+1][t-1][1] + prices[i])
	3. base
	- (t <= 0) 0
	- (i > prices.leng() - 1) 0
	*/
	vector<vector<vector<int>>> memo;
	vector<int> p;
	int dp(int i, int t, int h){
	// base
	if(i == p.size() or t == 0)
	return 0;
	// relation
	if(memo[i][t][h] == INT_MIN){
	int donothing = dp(i + 1, t, h);
	// sell
	if(h == 1)
	memo[i][t][h] = max(donothing, p[i] + dp(i + 1, t - 1, 0));
	// buy
	else
	memo[i][t][h] = max(donothing, -p[i] + dp(i + 1, t, 1));
	}
	return memo[i][t][h];
	}
	int maxProfit(int k, vector<int>& prices) {
	int n = prices.size();
	p = prices;
	memo.resize(n);
	for(auto &m: memo){
	m.resize(k + 1);
	for(auto &i: m)
	i.resize(2, INT_MIN);
	};
	return dp(0, k, 0);
	}
	};

view raw 188. Best Time to Buy and Sell Stock IV.cpp hosted with ❤ by GitHub