309. Best Time to Buy and Sell Stock with Cooldown
Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm lợi nhuận tối đa khi mua bán cổ phiếu, với điều kiện:
Solution
1function maxProfit(prices: number[]): number {
2 if (prices.length === 0) return 0;
3 let f = 0, f0 = 0, f1 = -prices[0];
4 for (let i = 1; i < prices.length; i++) {
5 const price = prices[i];
6 const new_f0 = Math.max(f0, f1 + price);
7 const new_f1 = Math.max(f1, f - price);
8
9 f = f0;
10 f0 = new_f0;
11 f1 = new_f1;
12 }
13 return f0;
14}
15Solution
1function maxProfit(prices: number[]): number {
2 const n = prices.length;
3 const memo: number[][] = Array.from({length: n}, () => Array(2).fill(-1));
4 function dfs(i: number, holding: number): number {
5 if(i >= n) return 0;
6 if(memo[i][holding] !== -1) return memo[i][holding];
7 let res = dfs(i + 1, holding);
8 if(holding) {
9 res = Math.max(res, prices[i] + dfs(i + 2, 0))
10 } else {
11 res = Math.max(res, -prices[i] + dfs(i + 1, 1))
12 }
13 return memo[i][holding] = res;
14 }
15 return dfs(0, 0);
16};