[JS]股票交易最大收益

该题是典型的dp，首先常规思维来说，我们需要一个n x prices.length大小的array。
dp[k][i]就代表在到i个价格为止进行了k次交易获得的收益。
每次在计算当前dp[k][i]的时候有两种情况。

1. 当前价格没有交易发生，从上一个cell取值，即dp[k][i-1]

2. 发生交易，从j时买入，i时卖出，即 prices[i]-prices[j]+dp[k-1][j-1]
   每次遍历的时候去这两种情况的最大值即为当前最大利益。
   那么直接把这个思路转化成代码

   var maxProfit = function(prices) {
    let dp = new Array(3)
   
    for(let k=0;k<dp.length;++k) dp[k] = new Array(prices.length).fill(0)
   
    for(let k = 1;k<dp.length;++k){
   
        for(let i = 1;i<dp[0].length;++i){
            let min = prices[0]
            for(let j = 1;j<=i;++j){
                min = Math.min(min, prices[j]-dp[k-1][j-1])
            }
            dp[k][i] = Math.max(dp[k][i-1],prices[i]-min)
   
        }
   
    }
    return dp[2][prices.length-1]
   };

   时间复杂度O(kn^2)，可以看到这种方法时间复杂度很高，继续优化。
   首先min的意思是如果要进行当前这笔交易，我们的成本是多少？
   成本即为：prices[j]-dp[k-1][j-1]，意思是我们买入的价格减去k-1次交易后我们手头的利润。
   假设当前我们的位置是dp[k][i],那我们怎么求出当前的最小成本呢
   答案是比较dp[k][i-1]的最小成本和当前最新的情况i-1时买入成本
   即为Math.min(min,prices[i]-dp[k-1][i-1])
   此时我们可以省掉j的那圈循环，把复杂度降到kn

   function maxProfit( prices ) {
    // write code here
   
    let dp = new Array(3)
   
    for(let k=0;k<dp.length;++k) dp[k] = new Array(prices.length).fill(0)
   
    for(let k = 1;k<dp.length;++k){
        let min = prices[0]
        for(let i = 1;i<dp[0].length;++i){
            min = Math.min(min, prices[i]-dp[k-1][i-1])
            dp[k][i] = Math.max(dp[k][i-1],prices[i]-min)
        }
   
    }
    return dp[2][prices.length-1]
   

}
```