买卖股票的最佳时机IV

TIP

给定一个整数数组 prices ，它的第i个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

第一次持有股票
第一次不持有股票
第二次持有股票
第二次不持有股票
……
第k次持有股票
第k次不持有股票

var maxProfit = function(k, prices) {
    let dp =  Array(prices.length).fill().map(() => Array(2*k+1).fill(0))
    for(let i=1;i<2*k;i+=2){   //注意初始化！！！ 只要买入，现金就做相应的减少
            dp[0][i] -= prices[0]  
    }         
    for(let i=1;i<prices.length;i++){
        for (let j = 0; j <=2*k - 1; j += 2) {
                dp[i][j + 1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i]);
                dp[i][j + 2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);
            }
    }
    console.log(dp)
    return dp[prices.length-1][2*k]
};

买卖股票的最佳时机IV ​

思路 ​

买卖股票的最佳时机IV

思路