ภาพรวมปัญหา
ให้ราคาหุ้นรายวัน หากำไรสูงสุดจากการซื้อขายได้สูงสุด k ครั้ง (ต้องขายก่อนซื้อครั้งใหม่)
ตัวอย่าง
prices = [3,2,6,4,0,3], k = 2 → 7
ซื้อวันที่ 2 (2) ขายวันที่ 3 (6) กำไร 4
ซื้อวันที่ 5 (0) ขายวันที่ 6 (3) กำไร 3
วิธีแก้ปัญหา: DP 3 มิติ + Optimization
dp[i][k][holding] = กำไรสูงสุดวันที่ i เหลือธุรกรรม k สถานะ holding (0=ไม่ถือ, 1=ถือ)
Optimization: k ≥ n/2
ถ้า k มากพอ → กลายเป็น unlimited transactions: บวกกำไรทุกครั้งที่ราคาขึ้น
โค้ด C++ (Memoization)
#include <bits/stdc++.h>
using namespace std;
typedef int lli;
const lli N = 1000;
lli dp[N+5][N+5][2];
class Solution {
public:
void pre() {
for (int i = 0; i <= N; i++)
for (int j = 0; j <= N; j++)
dp[i][j][0] = dp[i][j][1] = -1;
}
lli solve(vector<int>& arr, lli i, lli n, lli k, lli status) {
if (i == n) return status ? -100000 : 0;
if (dp[i][k][status] != -1) return dp[i][k][status];
lli ans = solve(arr, i+1, n, k, status);
if (status) ans = max(ans, solve(arr, i+1, n, k-1, !status) + arr[i]);
else if (k > 0) ans = max(ans, solve(arr, i+1, n, k, !status) - arr[i]);
return dp[i][k][status] = ans;
}
int maxProfit(int k, vector<int>& prices) {
pre();
if (k >= prices.size()/2) {
int ans = 0;
for (int i = 1; i < prices.size(); i++)
if (prices[i] > prices[i-1]) ans += prices[i] - prices[i-1];
return ans;
}
return solve(prices, 0, prices.size(), k, 0);
}
};
int main() {
Solution ob;
vector<int> v = {3,2,6,4,0,3};
cout << (ob.maxProfit(2, v));
}
ผลลัพธ์
7
การวิเคราะห์ความซับซ้อน
- เวลา: O(n×k) กรณีทั่วไป, O(n) กรณี k ≥ n/2
- พื้นที่: O(n×k)
