蓝桥杯动态规划每日一题

动态规划每日一题"/>

蓝桥杯动态规划每日一题

一、买卖股票的最佳时机III

股票最佳时机

1.状态表示

dp[i]:到达i天，所能获得的最大利润

但是我们唯一不清楚的是，他完成了几笔交易，所以不如，就设置一种二维数组

dp[m][3]

2是说第0天是第0笔，第一天是第1笔，第二天就第二笔呗。

但是我们写状态转移方程的时候发现，不好表示dp[i]和dp[i-1]之间的关系，所以进一步去细分

f[3][i]:到达i位置，买入后没有进行别的操作处于可以卖出状态

g[3][i]：到达i位置，手里没有股票处于可以买入状态

2.状态转移方程

f[i][m]=(g[i-1][m]-price[i],f[i-1][m])

g[i][m]=(f[i-1][m-1]+price[i],g[i-1][m])

3.初始化

0天0笔交易，所以默认都是0呗

但是有几个问题

初始化，要把f[0][j]，也就是第0天的第一笔，第n笔交易都变为不去干扰整个表的值，也就是负无穷，但是负无穷的运算可能会让数据发生越界错误，所以要有一个足够大的数，还可以去运算所以这时候这个数0x3f3f3f3f，这个数足够大，加上负号就足够小，

f[0][0]是已经买入状态，所以他的值应该是扣钱，-price[0][0],其余0天都是-∞，第0天可以理解为第一天。当然第0笔不能这么认为哈。

4.填表顺序

从左到右，两个表一起填写。

5.返回值，返回g表g[m-1][j]中最大值即可

class Solution {public int maxProfit(int[] prices) {int m=prices.length;int[][]f=new int[m][3];int[][]g=new int[m][3];int INF=0x3f3f3f3f;for(int j=0;j<3;j++){f[0][j]=g[0][j]=-INF;}f[0][0]=-prices[0];g[0][0]=0;for(int i=1;i<m;i++){for(int j=0;j<3;j++){//状态方程可以看到，这个初始化并不容易。只有一个j-1所以不需要为了他，单独去初始化g[i][j]=g[i-1][j];f[i][j]=Math.max(g[i-1][j]-prices[i],f[i-1][j]);if(j-1>=0){g[i][j]=Math.max(f[i-1][j-1]+prices[i],g[i-1][j]);}}}
int ret=0;
for(int j=0;j<3;j++){ret=Math.max(ret,g[m-1][j]);
}return  ret;}
}