1.在推狀態轉移方程的途中，箭頭的起始點表示前一天的狀態，箭頭的終點是當天的狀態
2.當動態規劃中涉及到多狀態，且狀態之間可以相互轉換，要畫圖去分析
1.買賣股票的最佳時機含冷凍期
題目鏈接：309. 買賣股票的最佳時機含冷凍期 - 力扣（LeetCode）
題目解析：prices數組的數據表示當天股票的價格，要對一個股票不斷進行交易，且當我們在前一天將股票賣出。那么第二天就會進入冷凍期，冷凍期間不能做任何的交易，計算并返回股票交易能夠獲得的最大利益。
算法講解：動態規劃
1.狀態表示：經驗+題目要求
在這道題中，可以將dp[i]表示為到第i天結束時，此時獲得的最大利潤，但是這道題中，涉及到 “買入”（買入就是會在當天手中有股票，既可以將股票賣出去，也可以不將股票賣出去），“可交易”（可交易就是手中沒有股票，可以在當天買入股票，也可以不在當天買入股票），“冷凍期”（冷凍期就是當天不能做任何的交易）這三個狀態，所以也可以將狀態表示細分為3個狀態
dp[i][0]表示：第i天結束后，處于“買入”狀態，此時獲得的最大利潤
dp[i][1]表示：第i天結束后，處于“可交易”狀態，此時獲得的最大利潤
dp[i][2]表示：第i天結束后，處于“冷凍期”狀態，此時獲得的最大利潤
2.狀態轉移方程：
由于涉及到的狀態有點多，可以畫一張圖來分析各個狀態，如下圖，分析狀態之間能夠相互轉換，以當天的狀態為買入為例，就要分別分析前一天的狀態為買入，冷凍期和可交易時，能否轉換為當天的買入狀態
第一種情況：第i天是買入狀態，即推算dp[i][0]
首先分析，能否由買入狀態轉換為買入狀態，也就是當第i-1天的狀態為買入狀態時，能否轉換為第i天的買入狀態，此時是可以轉換的，當前一天為買入狀態時，只要前面一天不做任何的交易，那么第二天也是買入的狀態。
其次分析，?能否由可交易狀態轉換為買入狀態，也就是當第i-天是可交易狀態時，能否轉換為第i天的買入狀態，此時是可以轉換的，當前一天為可交易狀態時，只要在前一天買入股票，第二天就可以處于買入狀態了。
最后分析，能否有冷凍期狀態轉換為買入狀態，此時是不可以轉換的，如果前一天為冷凍期狀態，前一天是不可以做任何交易的，所以在冷凍期的那一天是不可以買入股票的，由于前一天為冷凍期不能購入股票，所以第二天是不可能轉換為買入狀態的
如下圖，根據下圖來推算dp[i][0]時，也就是計算第i天結束后，處于“買入”狀態，此時獲得的最大利潤，要計算dp[i][0]，此時就要知道前一天的最大利潤，因為只有買入狀態和可交易狀態能裝換為買入狀態，此時就要知道前一天處于買入狀態獲得的最大利潤或者前一天處于可交易狀態時獲得的最大利潤，根據狀態表示，就可以推算出dp[i][0]的狀態轉移方程：
dp[i][0] = Math.max( dp[i-1][0] , dp[i-1][1] - prices[i] )
第二種情況：第i天是可交易狀態，即推算dp[i][1]
首先分析，能否從買入狀態轉換為可交易狀態，此時是不可以轉換的，要想從買入狀態轉換為可交易狀態，前一天就要將股票賣出去，但是根據題目要求如果在前一天將股票賣出去，第二天就會處于冷凍期狀態了
其次分析，能否從可交易狀態轉換為可交易狀態，當前一天是可交易狀態時，只要在前一天不做任何的交易，第二天任然可以處于可交易的狀態
最后分析，能否從冷凍期轉換為可交易狀態，前一天為冷凍期狀態時，啥都不做，第二天就是可交易狀態了，此時是可以轉換成功的
此時去推算dp[i][1]時，也就是計算 第i天結束后，處于“可交易”狀態，此時獲得的最大利潤，此時就要知道前一天為可交易狀態獲得的最大利潤或者前一天為冷凍期狀態獲得的最大利潤，此時dp[i][1]狀態轉移方程為：
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][2])
第三種情況：第i天是冷凍期狀態，即推算dp[i][2]
首先分析，能否從買入狀態轉換為冷凍期狀態，當前一天的狀態是買入狀態時，只要在前一天將股票賣出去，第二天就可以處于冷凍期狀態了
其次分析，能否從可交易狀態轉換為冷凍期狀態，當前一天是可交易狀態時，由于手中是沒有股票的，根本沒有辦法做出買股票的行為，所以此時就無法從前一天的可交易狀態轉換為第二天的冷凍期狀態
最后分析，能否從冷凍期轉換為冷凍期轉態，此時不可能轉換成功的，如果前一天的狀態是冷凍期狀態，冷凍期雖然啥交易都不能做，但是根據題目的要求，前一天是冷凍期，第二天就會是可交易狀態了
此時去推算dp[i][2]時，也就是計算 第i天結束后，處于“冷凍期”狀態，此時獲得的最大利潤，此時因為只能從買入狀態轉換為冷凍期狀態，所以此時要知道前一天為買入狀態時獲得的最大利潤，此時dp[i][2]的狀態轉移方程:
dp[i][2]=dp[i-1][0]+prices[i]
3.初始化
此時要初始化dp[0][0]，dp[0][1]，dp[0][2]，dp[0][0]表示第一天之后就處于買入狀態時獲得的最大利潤，所以此時dp[0][0]=-prices[0]，dp[0][1]表示第一天之后處于可交易狀態時獲得的最大利潤，第一天手中根本沒有股票，所以將dp[0][1]=0，dp[0][2]表示第一天之后處于冷凍期狀態此時獲得的最大利潤，第一天手中根本沒有股票，所以將dp[0][2]初始化為0
4.填表順序
從左往右，同時填3個表即可
5.返回值
返回Math.max(dp[n-1][0],Math.max(dp[n-1][1],dp[n-1][2]))即可
代碼實現：
//我寫的版本
class Solution {public int maxProfit(int[] prices) {int n=prices.length;int[] buy=new int[n+1];//買入int[] sell=new int[n+1];//可交易int[] ice=new int[n+1];//冷凍sell[0]=0;buy[0]=Integer.MIN_VALUE;ice[0]=0;for(int i=1;i<n+1;i++){buy[i]=Math.max(buy[i-1],sell[i-1]-prices[i-1]);sell[i]=Math.max(sell[i-1],ice[i-1]);ice[i]=buy[i-1]+prices[i-1];}return Math.max(buy[n],Math.max(sell[n],ice[n]));}
}//第一個版本
class Solution {public int maxProfit(int[] prices) {int n=prices.length;int[][] dp=new int[n][3];dp[0][0]=-prices[0];dp[0][1]=0;dp[0][2]=0;for(int i=1;i<n;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][2]);dp[i][2]=dp[i-1][0]+prices[i];}return Math.max(dp[n-1][0],Math.max(dp[n-1][1],dp[n-1][2]));}
}//第二個版本
class Solution {public int maxProfit(int[] prices) {int n=prices.length;int[][] dp=new int[3][n];dp[0][0]=-prices[0];dp[1][0]=0;dp[2][0]=0;for(int i=1;i<n;i++){dp[0][i]=Math.max(dp[0][i-1],dp[1][i-1]-prices[i]);dp[1][i]=Math.max(dp[1][i-1],dp[2][i-1]);dp[2][i]=dp[0][i-1]+prices[i];}return Math.max(dp[0][n-1],Math.max(dp[1][n-1],dp[2][n-1]));}
}
2.買賣股票的最佳時機含手續費
題目鏈接：714. 買賣股票的最佳時機含手續費 - 力扣（LeetCode）?
題目解析：當完成一個股票的買入和賣出之后，才算一筆交易，當手中有股票時，必須先把股票賣出才能繼續買入股票，計算并返回多次交易后能獲得的最大利潤，且每次交易都會付出手續費
算法講解：動態規劃
1.狀態表示：經驗+題目要求
題目要求我們返回獲得的最大利潤，所以dp[i]表示：第i天結束后，能獲得的最大利潤，但是在第i天的時候，是有買入狀態和賣出狀態這兩種情況，所以，此時狀態表示也要分為兩種情況：
第一種情況：用buy[i]表示：第i天結束后，處于“買入”的狀態，此時能夠獲得的最大利潤
第二種情況：用sell[i]表示：第i天結束后，出入“賣出”的狀態，此時能夠獲得的最大利潤
2.狀態轉移方程
因為涉及到多狀態且涉及到狀態之間的轉換，此時可以畫圖來分析不同狀態之間能否相互轉換，如下圖
第一種情況：當天處于買入狀態，推算buy[i]
首先分析，能否從第i-1天的買入狀態轉換為第i天買入轉態，當第i-1天處于買入狀態時，只要在第i-1天啥交易都不要做，第二天還是買入狀態，此時是可以相互轉換的
最后分析，能否從第i-1天的賣出狀態轉換為第i天的買入狀態，當第i-1天為賣出狀態時，因為第i-1天處于賣出狀態，說明這一天已經把股票賣出去了，此時要想轉換為買入狀態，只要在第i-1天買入股票就行了，然后第i天就是買入狀態了
如下圖
此時推算buy[i]時，也就是計算第i天結束后，處于“買入”的狀態，此時能夠獲得的最大利潤，如果要知道第i天的最大利潤，首先就要知道第i-1天時能夠獲得的最大利潤，通過上面的分析知道，在計算buy[i]時，就要知道第i-1天之后處于買入狀態時獲得的最大利潤或者第i-1天之后處于賣出狀態時能夠獲得的最大利潤，由于要求最大利潤和根據狀態表示，buy[i]的狀態轉移方程：
buy[i]=Math.max(buy[i-1]，sell[i-1])
第二種情況：當處于賣出狀態時，推算sell[i]
因為一次交易涉及到手續費，可以在買入股票或者賣出股票時去支付這個手續費，下面我是在賣出股票時支付手續費?
首先分析，能否從第i-1天的買入狀態轉換為第i天的賣出狀態時，當第i-1天處于買入狀態時，只要在第i-1天將手中的股票賣出，第i天就可以處于賣出狀態了（此時要支付手續費）
最后分析，能否從第i-1天的賣出狀態轉換為第i天的賣出狀態，當第i-1天處于賣出狀態，只要在第i-天啥交易都不做，就可以在第i天保持賣出的狀態
根據上面的分析，推算sell[i]時，也就是計算第i天結束后，處于“賣出”的狀態，此時能夠獲得的最大利潤，如果要計算第i天能夠獲得的最大利潤，首先就要知道第i-1天時能夠獲得的最大利潤，因為第i-1天有兩種情況，此時就要知道第i-1天之后處于“買入”時能獲得的最大利潤或者第i-1天之后處于“賣出”狀態時能夠獲得的最大利潤，此時計算利潤時要記得支付手續費
sell[i]=Math.max(sell[i-1],buy[i-1]+prices[i]-fee)
總結如下圖
3.初始化
此時由于初始化比較簡單，就不用多創建空間來實現初始化了，根據細分的狀態表示，只要將buy[0]=-prices[0]，sell[0]=0即可
4.填表順序
從左往右，同時填兩個表即可
5.返回值
返回Math.max(buy[n-1],sell[i-1])即可
代碼實現：
class Solution {public int maxProfit(int[] prices, int fee) {int n=prices.length;int[] buy=new int[n];int[] sell=new int[n];buy[0]=-prices[0];sell[0]=0;for(int i=1;i<n;i++){buy[i]=Math.max(buy[i-1],sell[i-1]-prices[i]);sell[i]=Math.max(sell[i-1],buy[i-1]+prices[i]-fee);}return Math.max(buy[n-1],sell[n-1]);}
}3.買賣股票的最佳時機 IV
題目鏈接：188. 買賣股票的最佳時機 IV - 力扣（LeetCode）?
題目解析：最多可以做k次交易，每一次買入股票必須將手中的股票賣出去之后才能進行下一次的交易，計算并返回進行k次交易后能夠獲得的最大利潤
講解算法原理：
1.狀態表示：經驗+題目要求
根據題目要求，可以將dp[i]表示為第i天結束后，能夠獲得的最大利潤，但是此時狀態表示還可以細分，因為第i天結束1后，是會有兩種情況的，分別是“有股票”和“沒有股票”?這兩種情況，此時就可以用f[i]來表示第i天結束后，處于“有股票”的狀態，此時能夠獲得的最大利潤，用g[i]表示第i天結束后，處于“沒有股票的狀態”，此時能夠獲得的最大利潤。
但是因為存在交易次數的限制，所以在定義狀態表示時，還要將交易次數表示出來，所以最終的狀態表示為：
f[i][j]表示：第i天結束后，完成了j次交易，處于“有股票”的狀態，此時獲得的最大利潤
g[i][j]表示：第i天結束后，完成了j次交易，處于“沒有股票”的狀態，此時獲得的最大利潤
2.推算狀態轉移方程
此時涉及到多狀態之間轉換的分析，依舊老樣子，畫圖分析，如下圖
第一種情況：第i天處于有股票狀態，推算f[i][j]?
首先分析，能否從有股票的狀態轉換為有股票的狀態，當第i-1天處于有股票的狀態時，要想在第i天還是處于有股票的狀態，只要在第i-1天不做任何交易就行了，這樣就能在第i天依舊保持有股票的狀態，所以此時是可以轉換的
最后分析，能否從沒有股票的狀態轉換為有股票的狀態，當第i-1天處于沒有股票的狀態時，要想在第i天處于有股票的狀態，只要在第i-1天買入股票，第i天就可以處于有股票的狀態，所以此時是可以轉換的
如下圖
則此時f[i][j]的狀態轉移方程：
f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i])?
第二種情況：第i天處于沒有股票狀態，推算g[i][j]
首先分析，能否從沒有股票的狀態裝換為沒有股票的狀態，當第i-1天處于沒有股票的狀態時，只要不在第i-1天作任何的交易，第i天就可以處于沒有股票的狀態，此時是可以轉換的
其次分析：能否從有股票的狀態轉換為沒有股票的狀態，當第i-1天處于有股票的狀態，要想在第i天處于有股票的狀態，只要在第i-1天降股票賣出去即可，然后第i天就可以處于沒有股票的狀態了，但是此時要考慮交易次數，因為會將股票賣出去，此時完成一次交易，所以此時交易次數是要增加一次的
如下圖
則此時g[i][j]的狀態轉移方程：
g[i][j]=Math.max(g[i-1][j],f[i-1][j-1]+prices[i])?
?推算g[i][j]的f[i-1][j-1]中為什么是j-1呢？
這里的i-1是指上一次交易，g[i][j]是指當前的交易，在有股票向沒有股票的狀態轉換時，是完成了一次交易的，也就是推算這一次的g[i][j]，為了推算第i次交易的最大利潤，是要知道前一次交易的最大利潤的，也就是f[i-1][j-1]
為了方便后面的初始化，可以轉換一下g[i][j]的狀態轉移方程，將其分為兩步：
第一步：g[i][j]=g[i-1][j]
第二步：if(j-1>=0) g[i][j]=Math.max(g[i][j]，f[i-1][j-1]+prices[i])?
3.初始化
由于在計算f[i][j]和g[i][j]時，由于會用到[i-1]行的值，所以要初始化第一行的值
初始化f[i][j]的第一行的值時，首先根據我們的狀態f[i][j]的狀態表示，要將f[0][0]=-prices[0]，f[0][0]就表示第一天買入股票步不進行任何交易獲得的最大利潤，由于是有交易次數的限制的，盡量不要在當天買入股票或者賣出股票之后去進行交易，因為同一天的股票價格是一樣的，是不會獲得利益的，由于在推算g[i][j]和f[i][j]時，用到的是max，因為不允許在同一天進行買入股票和賣出股票，所以盡量讓同一天進行一次交易和進行兩次交易的利潤變得很小，讓f[0][0]盡可能被選到，即讓f[0][1]和f[0][2]都盡量初始化為很小，所以此時將dp[0][1]和dp[0][2]初始為一個最小值，這個最小值如何選擇呢？此時不能選擇Integer.MIN_VALUE，因為此時計算時有減的操作，Integer.MIN_VALUE減去一個數就會越界，所以此時選擇0x3f3f3f3f，這個16進制數是max的一半
同理可得。初始化g[i][j]的第一行的值時，將g[0][0]=0，g[0][1]=-0x3f3f3f3f，g[0][2]=-0x3f3f3f3f，此時根據g[i][j]的第一種狀態轉移方程，本來還要初始化第一列的數據的，但是用了第二種的狀態轉移方程，只要對i-1的值進行一個合法判斷就行了，此時，就不用初始化g表的第一列的數據了?
?4.填表順序
大方向從上往下填每一行，填每一行時從左往右同時填兩個表
5.返回值
返回g表中最后一行中的最大值即可，不用考慮f表，因為f表最終狀態還是有股票的狀態，沒把股票賣出去，此時的利潤肯定是沒有最后將股票賣出去的利潤大的
代碼實現：
class Solution {public int maxProfit(int k, int[] prices) {int n=prices.length;int[][] f=new int[n][k+1];int[][] g=new int[n][k+1];for(int i=0;i<k+1;i++) f[0][i]=-0x3f3f3f3f;for(int i=0;i<k+1;i++) g[0][i]=-0x3f3f3f3f;f[0][0]=-prices[0];g[0][0]=0;for(int i=1;i<n;i++){for(int j=0;j<k+1;j++){f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j]=g[i-1][j];if(j-1>=0) g[i][j]=Math.max(g[i][j],f[i-1][j-1]+prices[i]);}}int max=g[n-1][0];for(int i=0;i<k+1;i++){if(max<g[n-1][i]) max=g[n-1][i];}return max;}
}4.買賣股票的最佳事假 III
該題的分析與第3題一模一樣，不過就是將k變為2即可
代碼實現：
class Solution {public int maxProfit(int[] prices) {int n=prices.length;int[][] f=new int[n][3];int[][] g=new int[n][3];for(int i=0;i<3;i++) f[0][i]=-0x3f3f3f3f;for(int i=0;i<3;i++) g[0][i]=-0x3f3f3f3f;f[0][0]=-prices[0];g[0][0]=0;for(int i=1;i<n;i++){for(int j=0;j<3;j++){f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j]=g[i-1][j];if(j-1>=0) g[i][j]=Math.max(g[i][j],f[i-1][j-1]+prices[i]);}}int max=g[n-1][0];for(int i=0;i<3;i++){if(max<g[n-1][i]) max=g[n-1][i];}return max;}
}
