算法类

1、买卖股票：

1.1买1次

动态规划：
  dp[i][0]：规定了今天不持股，有以下两种情况：  昨天不持股，今天什么都不做；
     昨天持股，今天卖出股票（现金数增加），
     状态转移方程：dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  dp[i][1]：规定了今天持股，有以下两种情况：
     昨天持股，今天什么都不做（现金数与昨天一样）；
     昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）
     状态转移方程：dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
贪心：
  每次记录当天卖出时的最大值，并同时更新全局最大值。

1.2买无数次

动态规划：  
step 1： 用dp[i][0]表示第i天不持股到该天为止的最大收益，dp[i][1]表示第i天持股，到该天为止的最大收益。
step 2：（初始状态） 第一天不持股，则总收益为0，dp[0][0]=0
                  第一天持股，则总收益为买股票的花费，此时为负数，dp[0][1]=−prices[0]

step 3：（状态转移） 对于之后的每一天，如果当天不持股，有可能是前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同，也有可能是当天卖掉股票，
        我们选择较大的状态  dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i])
                       
step4：如果当天持股，可能是前几天买入的还没卖，因此收益与前一天相同，也有可能是当天买入，减去买入的花费，同样是选取最大值：
                dp[i][1]=max(dp[i−1][1],dp[i−1][0]−prices[i])
贪心：

只要第二天比前一天高，就买卖， 原理：B-A+A-C = B-C

1.3买2次

public int maxProfit (int[] prices) {
        if(prices == null || prices.length <= 1) return 0 ;
        int n = prices.length ;
        int f[][] = new int[n][5] ;
        f[0][0] = 0 ;//f[i][0]:到第i天为止，没买过股票的最大收益
        f[0][1] = -prices[0] ;//f[i][1]:到第i天为止，买过一次的最大收益
        f[0][2] = f[0][0] ;//f[i][2]:到第i天为止，买过一次，买过一次的最大收益
        f[0][3] = f[0][1] ;//f[i][3]:到第i天为止，买过两次，买过一次的最大收益
        f[0][4] = f[0][0] ;//f[i][4]:到第i天为止，买过两次，买过两次的最大收益
        for(int i = 1 ; i < n ; i ++) {
            f[i][0] = f[i-1][0] ;
            f[i][1] = Math.max(f[i-1][1] , f[i-1][0] - prices[i]) ;
            f[i][2] = Math.max(f[i-1][2] , f[i-1][1] + prices[i]) ;
            f[i][3] = Math.max(f[i-1][3] , f[i-1][2] - prices[i]) ;
            f[i][4] = Math.max(f[i-1][4] , f[i-1][3] + prices[i]) ;
        }
        int max = Math.max(f[n-1][2] , f[n-1][4]) ;
        return  max > 0 ? max : 0 ;
    }

1.4买k次