DAY41-动态规划-买卖股票

LeetCode121. 买卖股票的最佳时机

    public int maxProfit(int[] prices) {//dp数组含义：0为持有该股票，1为不持有该股票int[][] dp = new int[prices.length][2];dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.length;i++) {dp[i][0]=Math.max(dp[i-1][0], -prices[i]);dp[i][1]=Math.max(dp[i-1][1], dp[i][0]+prices[i]);}return dp[prices.length-1][1];}

LeetCode122.买卖股票的最佳时机II

    public int maxProfit(int[] prices) {//dp数组含义：0为持有该股票，1为不持有该股票int[][] dp = new int[prices.length][2];dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.length;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][0]+prices[i]);}return dp[prices.length-1][1];}

LeetCode123.买卖股票的最佳时机III

    public int maxProfit(int[] prices) {//dp数组含义：0为无状态，1为持有，2为不持有，3为持有，4为不持有int[][] dp = new int[prices.length][5];dp[0][0]=0;dp[0][1]=-prices[0];dp[0][2]=0;dp[0][3]=-prices[0];dp[0][4]=0;for(int i=1;i<prices.length;i++) {dp[i][0]=dp[i-1][0];dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);dp[i][2]=Math.max(dp[i-1][2], dp[i][1]+prices[i]);dp[i][3]=Math.max(dp[i-1][3], dp[i-1][2]-prices[i]);dp[i][4]=Math.max(dp[i-1][4], dp[i][3]+prices[i]);}return dp[prices.length-1][4];}