困难题我哭了，虽然有点思路，但是最后的代码还是超时了，记录下吧

LeetCode上最佳时机 III，之前做了最佳时机I和最佳时机II，这道是困难题记录下解题思路。这是一个动态规划问题，之前写过的斐波那契数就是一个类似一位数组下的动态规划问题。

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

就像斐波那契数的公式f(n) = f(n-1) + f(n-2)一样，在n情况下的值，是前两次值的和。当我们求f(5)的值的时候就能拆分成下图所示，f(0)和f(1)都是很好计算或者已知的值。通过将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案的过程就是动态规划的思想了。

将上面斐波那契的例子扩展成二维数组情况下，就能求解当前问题。
首先最多可交易2次，那么就有0/1/2次三种可交易的形式，假设现在传入的价格数组是prices = [7,1,5,3,2,4,8]，可以构建出如下二维数组表格，最上排灰色字体对应价格数组的序号

建立数组

第一排第一例填充0

1. 当天不操作 当天不操作的情况就是继承前一天操作1次时候的收益
2. 当天操作 当天操作的情况就是不操作的情况的收益 + 今天卖出的收益
   对于不操作的情况的收益，根据天数不同，需要判断的数据也不同，例如现在填写序号2的数据，那么就要对比在序号0、1的时候，操作为0的时候的收入，取其中最大的值

在这2种操作中间取最大值，就是今天操作1次的最大收益，根据上面的计算步骤可以填写如下表格

填充第二排

结合2排数据可以得到以下结论

当天的收益结果可以为以下情况

1. 当天不操作继承前天的收益
2. 当天操作一次+前几天操作一次的收益，然后取这些的最大值

可以得出以下代码片段

let maxp = 0
for(let n =j-1; n>=0; n--) {
// 对比几次的收益，获取最大值
// prices[j] 是今天的价格
// prices[n] 是第n天的价格
// dp[i-1][n] 是第n天的最大收益，指前一天操作一次的时候的收益
maxp = Math.max(prices[j]-prices[n]+dp[i-1][n],maxp)
}
// 和前今天一次都不操作的收益进行对比，求最大值
Math.max(dp[i][j-1],maxp)

这样我们了解了所有的原理之后就能得到如下完整代码

 var maxProfit = function(prices) {
    // 保存数组长度 
    let n = prices.length
    // 如果为空返回0
    if(n == 0) return 0
    // 第一个参数为行数，第二个参数为列数，快速定义二维数组，快速创建二维数组小技巧
    let dp = Array.from(Array(3),() => new Array(n));
    // 第一行填充0
    for (let i = 0; i < n; i++) {
      dp[0][i] = 0
    }
    // 第一列填充0
    for (let j = 0; j < 3; j++) {
      dp[j][0] = 0
    }
    console.log(dp);
    // 然后开始填充数组
    for(let j = 1; j < 3; j++) {
      // 从第二排开始，先填充操作一次的数据
      for(let i = 1; i < n; i++) {
        // 设置最大收益
        let maxp = 0
        // 第i行的第j个数据的最大值
        for(let n = i-1; n >= 0; n--){
          maxp = Math.max(prices[i]-prices[n]+dp[j-1][n],maxp)
        }
        // 和前一天的数据对比，填入最大值
        dp[j][i] = Math.max(dp[j][i-1],maxp)
      }
    }
    console.log(dp);
    return dp[2][n-1];
};

这个代码得到的结果和之前我们填写的表格一样，最后一排的最后一位就是需要的结果

上面的代码对于小数据还是能够处理的，但是传入LeetCode上提交的时候出现了超时的问题，主要还是出现在下面这个for循环上，多次嵌套遍历需要的时间太多了。

// 第i行的第j个数据的最大值
for(let n = i-1; n >= 0; n--){
  maxp = Math.max(prices[i]-prices[n]+dp[j-1][n],maxp)
}

下面开始优化
自己优化太水了，参考的Leetcode刷题 123.买卖股票的最佳时机 III Best Time to Buy and Sell Stock III
这里应该使用一个变量来保存之前天数的最大利润，就像回到最开始斐波那契数的公式f(n) = f(n-1) + f(n-2)，如果保存了f(n-1)和f(n-2)的数据的时候，就不用每次都去前面推算这两个数据了，可以大大减少计算量。
可以将代码优化如下。

 var maxProfit = function(prices) {
    // 保存数组长度 
    let n = prices.length
    // 如果为空返回0
    if(n == 0) return 0
    // 第一个参数为行数，第二个参数为列数，快速定义二维数组，快速创建二维数组小技巧
    let dp = Array.from(Array(3),() => new Array(n));
    // 第一行填充0
    for (let i = 0; i < n; i++) {
      dp[0][i] = 0
    }
    // 第一列填充0
    for (let j = 0; j < 3; j++) {
      dp[j][0] = 0
    }
    // 然后开始填充数组
    for(let j = 1; j < 3; j++) {
      // 设置最大收益
      let maxp = -prices[0]
      // 从第二排开始，先填充操作一次的数据
      for(let i = 1; i < n; i++) {
        // 和前一天的数据对比，填入最大值
        dp[j][i] = Math.max(dp[j][i-1],prices[i] + maxp)
        maxp = Math.max(maxp,dp[j-1][i]-prices[i])
      }
    }
    console.log(dp);
    return dp[2][n-1];
};

几个优化的点：

1. let maxp = -prices[0]设置最大收益
2. 用maxp保存前i-1天的最大收益，从而减少计算量

参考文章：

1. 从斐波那契数列看递归和动态规划