LeetCode 123 买卖股票的最佳时机|||

1.根据前面两个题的动态规划思想做的 

class Solution { public int maxProfit(int[] prices) { if(prices.length==0) return 0; int[][][] dp = new int[prices.length][3][2]; for(int i=0;i<prices.length;i++){ for(int k=1;k<3;k++){ if(i==0){ dp[i][k][0]=0; dp[i][k][1]=-prices[i]; }else{ dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]); dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]); } } } //return dp[prices.length-1][1][0]>dp[prices.length-1][2][0]?dp[prices.length-1][1][0]:dp[prices.length-1][2][0]; return dp[prices.length-1][2][0]; } }

 

1.有一点我是没有想明白的，就是为啥最后一定交易两次比交易1次大？这个我有点没想明白

2.为啥这个k从1开始遍历，那么dp[i-1][0][0]=0,就是声明的0了，第k-1天没有进行过交易，手里没有股票，确实是0

这个复杂度确实不太行

2.看的别人的，状态转移

class Solution { public int maxProfit(int[] prices) { int buy=Integer.MAX_VALUE,pro=0,buy2=Integer.MAX_VALUE,pro2=0; for(int price:prices){ buy=Math.min(buy,price); pro=Math.max(pro,price-buy); buy2=Math.min(buy2,price-pro); pro2=Math.max(pro2,price-buy2); } return pro2; } }

 

 buy指的是你买入这只股票的价格，所以只有当前股票比buy的便宜，才会更新buy

pro指的是利润，就是当前股票的价格高于你买的buy，你把pro-buy与当前的pro比了比，看看决定卖不卖

所以buy2和pro2也是在这个基础上延伸的，至于为啥buy2=Math.min(buy2,price-pro)

可以这么理解，当你进行第二只股票交易的时候，你手里肯定有钱，你去买第二只股票，原来的buy2  应该和   当前的股票减去手里的钱比  如果原来入手的第二只股票的价格，低于，你现在入手这一只-手里的钱

其实，我也还是不是很能理清楚