Dynamic Programming

Question 1

Stock Buy and Sell - One Transaction

Answer 1

record the minimum seen so far as buy, and calculate profit for sell at day i

Question 2

Stock Buy and Sell - Unlimited Transaction (non-overlapping)

Answer 2

not sell as long as price is increasing (local maximum - previous local minimum)

Question 3

Stock Buy and Sell - Most K transaction (non-overlapping)

Answer 3

DP
dp[k, i] best profit using prices until day i with at most k transactions
dp[0, :] = 0
dp[:, 0] = 0
dp[k, i] = max (
dp[k, i-1], – not do anything at day i
prices[i] + max(dp[k-1, j] - prices[j] for j < i) – buy at day j and sell at day i
)

Question 4

Stock Buy and Sell - Most 2 transactions (non-overlapping)

Answer 4

intermediate variables
buy1[i] = max(buy1[i-1], -prices[i]) – best choice for buy for 1st transaction until day i
sell1[i] = max(buy1[i-1] + prices[i], sell1[i-1]) – best choice for sell for 1st transaction until day i
buy2[i] = max(sell1[i-1] - prices[i], buy2[i-1])
sell2[i] = max(sell2[i-1] + prices[i], sell2[i-1])