I might be misunderstanding the problem statement, but my take: My impression is that for N max trades and M days of data, the "obvious" DP solution should be

I might be misunderstanding the problem statement, but my take: My impression is that for N max trades and M days of data, the "obvious" DP solution should be 2*N entries and O(NM) time, by tracking best profit for n trades whether you have the stock, where your update looks something like profit[trade_count=n, day=m, has_stock] = max(profit[trade_count=n, day=m-1, has_stock], profit[trade_count=n-1, day=n-1, has_stock] + transaction_cost[day=n, has_stock]) -- namely, as you've described in the article, either do nothing, or make a trade. Of course, you wouldn't store the full history -- you'd only need yesterday's data and today's update. Adding accounting to track the trade history is doable without bloating runtime too much, but it does increase space usage substantially. That said, if you don't have to keep to a strict number of trades, the DP solution should be able to fit in constant space (well, linear in number of days if you want to keep track of history for the best sequence of trades). I really like the idea in the article of adding a transaction cost and varying that to constrict the number of trades -- it reminds me of a cooling schedule for simulated annealing, and it's definitely not an approach I see interview candidates reaching for regularly.