股票问题
leetcode上的股票问题，归根到底就是给你一个数组，代表每一天股票的售价，问你买卖股票所能获得的最大利润，且每次交易只能卖了才能再次购买；不同题目会有不同的条件，如总共可以买卖k次，需要手续费，需要间隔一天等；
状态转移方程
每一天我们都有三个操作，即买入，卖出和无操作；对应这三个操作，每一天都有相应的状态，如某一天，在交易了k次之后，是否持有股票，已经在这个状态下所得到的最大利润；
可以用一个三维数组来表示，即dp[i][k][1] / dp[i][k][0] 表示在第i天，已交易k次的情况，且1，0 代表是否持有股票；
如dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。
状态转移方程如下
dp[i][k][0] = Max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
#解释：今天我没有持有股票，有两种可能：
#要么是我昨天就没有持有，然后今天选择 不操作，所以我今天还是没有持有；
#要么是我昨天持有股票，但是今天我卖了，所以我今天没有持有股票了。
dp[i][k][1] = Max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]
#解释：今天我持有着股票，有两种可能：
#要么我昨天就持有着股票，然后今天选择 不操作，所以我今天还持有着股票；
#要么我昨天本没有持有，但今天我选择买了，所以今天我就持有股票了。
base case
dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。
接下来先对应k的三种情况来套用这套公式
k=1
由于k=1，所以dp[i][1][1] = Max(dp[i-1][1][1],dp[i-1][0][0]-prices[i],而dp[i-1][0][0]=0
所以有dp[i][1][1] = Max(dp[i-1][1][1],-prices[i]
而且每个状态都直接和前一个状态有关，所以可以不用到整个数组。
func maxProfit(prices []int) int {
buy_i_0 := 0
buy_i_1 := -99999
for i:=1;i<=len(prices);i++{
buy_i_0 = Max(buy_i_0,buy_i_1+prices[i-1])
buy_i_1 = Max(buy_i_1,-prices[i-1])
}
return buy_i_0
}
k无限次
因为k无限制次数，所以可以认为 k 和 k - 1 是一样的；所以有
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
= max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
且这里每个状态都直接和前一个状态有关，所以可以不用到整个数组。
func maxProfit(prices []int) int {
dp_i_0 := 0
dp_i_1 := -99999
for i:=0;i<len(prices);i++{
tmp := dp_i_0
dp_i_0 = Max(dp_i_0,dp_i_1+prices[i])
dp_i_1 = Max(dp_i_1,tmp-prices[i])
}
return dp_i_0
}
k有限制次数
k有限制次数之后，就需要对k的状态进行遍历了。这里k=0的情况其实省略掉，直接从j=1开始，不过写上去方便理解一些；
这里多加了一个判断，当k大于天数的一半时，就可以理解为k为无限次了，因为买卖一次至少需要两天，所以当k大于天数的一半，就相当于无限次了；
就使用无限次的解法，不然当k过大，leetcode会报运行错误，超内存的错误；
func maxProfit(k int, prices []int) int {
if k>(len(prices)/2){
return maxProfit_inf(prices)
}
pro := make([][][2]int,len(prices)+1)
for i:=0;i<=len(prices);i++{
pro[i] = make([][2]int,k+1)
}
for i:=1;i<=len(prices);i++{
for j:=0;j<=k;j++{
if i-1==0{
pro[i][j][0] = 0
pro[i][j][1] = -prices[i-1]
continue
}
if j==0{
pro[i][j][0]=0
pro[i][j][1]=-99999
continue
}
pro[i][j][0] = Max(pro[i-1][j][0],pro[i-1][j][1]+prices[i-1])
pro[i][j][1] = Max(pro[i-1][j][1],pro[i-1][j-1][0]-prices[i-1])
}
}
return pro[len(prices)][k][0]
}
