动态规划求股票问题

###123题解（k=2）：



/**
 * @author xixing
 * @version 1.0
 * @date 2020/2/19 11:30
 */
public class N123 {
    public static int maxProfit(int[] prices) {

        int [][][] dp=new int[prices.length][3][2];
        dp[0][2][0]=0;
        dp[0][2][1]=-prices[0];
        dp[0][1][1]=-prices[0];
        dp[0][1][0]=0;
        for(int i=1;i<prices.length;i++){
            dp[i][2][0]=Math.max(dp[i-1][2][0],dp[i-1][2][1]+prices[i]);
            dp[i][2][1]=Math.max(dp[i-1][2][1],dp[i-1][1][0]-prices[i]);
            dp[i][1][0]=Math.max(dp[i-1][1][0],dp[i-1][1][1]+prices[i]);
            dp[i][1][1]=Math.max(dp[i-1][1][1],-prices[i]);

        }
        return dp[prices.length-1][2][0];


    }

大致思路

首先

dp[3][2][1]为第三天，最多可以购买两次，目前已经购买了彩票

建立动态规划表达式

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])

初始化数组

dp[0][1][1]=-prices[0] dp[0][1][0]=0 dp[0][2][1]=-prices[0] dp[0][2][0]=0

解释

第零天，最多有一次购买机会，我买了的情况，第零天，最多有一次购买机会，我没买

188题解1(超出内存限制):

public static int maxProfit(int k, int[] prices) {
   
    if(prices.length==0){
        return 0;
    }

    int dp[][][]=new int[prices.length][k+1][2];

    for(int i=0;i<prices.length;i++){
        for(int k1=k;k1>=1;k1--){
            if(i==0){
                dp[0][k1][0]=0;
                dp[0][k1][1] = -prices[i];
                continue;
            }
            dp[i][k1][0]=Math.max(dp[i-1][k1][0],dp[i-1][k1][1]+prices[i]);
            dp[i][k1][1]=Math.max(dp[i-1][k1][1],dp[i-1][k1-1][0]-prices[i]);
        }

    }

    return dp[prices.length-1][k][0];


}

188题解2：

public static int maxProfit(int k, int[] prices) {
    /**
     * java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
     *   at line 7, Solution.maxProfit
     *   at line 57, __DriverSolution__.__helper__
     *   at line 87, __Driver__.main
     */
    if(prices.length==0){
        return 0;
    }
    //当k>一半的时候，相当于可以每隔一天进行交易，直接调用122题的贪心算法即可

    if(k>prices.length/2){
        return maxProfit122(prices);
    }

    int dp[][][]=new int[prices.length][k+1][2];

    for(int i=0;i<prices.length;i++){
        for(int k1=k;k1>=1;k1--){
            if(i==0){
                dp[0][k1][0]=0;
                dp[0][k1][1] = -prices[i];
                continue;
            }
            dp[i][k1][0]=Math.max(dp[i-1][k1][0],dp[i-1][k1][1]+prices[i]);
            dp[i][k1][1]=Math.max(dp[i-1][k1][1],dp[i-1][k1-1][0]-prices[i]);
        }

    }

    return dp[prices.length-1][k][0];


}
public static int maxProfit122(int[] prices) {
    if (prices.length==0){
        return 0;
    }
    int temp=prices[0];
    int profile=0;
    for(int i=1;i<prices.length;i++){

        if(prices[i]>temp){
            profile=profile+prices[i]-temp;
            temp=prices[i];
        }else {
            temp=prices[i];
        }

    }
    return profile;
}