动态规划-求买卖股票所能获得的最大收益(hard)

一、问题描述

二、解题思路

1.先看有哪几个可变参数：

        (1).当前第几天 nowday(范围：0->n-1)

        (2).剩余交易次数 restTime(范围：k->0)

        (3).当天可买入还是可卖出 isnowHold(0 表示当前未持有可买入，1 表示当前持有可卖出)

2.需要三维dp数组来实现动态规划过程

        dp数组=[n][k+1][2]        n 表示天数维度        k+1表示剩余交易次数维度        2表示当天可买入还是卖出状态维度。

        price数组表示每一天的股票价格。

        (1).dp数组初始化(这一步很重要)：当天数为第一天时，可买入，无论交易次数剩(0~k-1)次，买入以后盈利值均为负数(负的第一天的股票价格)：

        dp[0][i][1]= -price[0]

        状态转移方程的推导过程如下：

        (2).要使第nowday天股票状态是未持有 (isnowHold=0) ，如果前一天未持有则直接迁移过来，如果前一天持有股票时的状态则需要卖出。

        比较两种方式的盈利值取最大值作为当前未持有时的状态 dp[nowday][restTime][0]

        状态转移公式：

        dp[i][j][0]=Max(dp[i−1][j][0],dp[i−1][j][1]+price[i])" role="presentation">dp[i][j][0]=Max(dp[i−1][j][0],dp[i−1][j][1]+price[i])$dp[i][j][0]=Max(dp[i-1][j][0],dp[i-1][j][1]+price[i])$

        (3).要使第nowday天股票状态是持有 (isnowHold=1) ，如果前一天持有则直接迁移，如果前一天没有，则需要买入。

        比较两种方式的盈利值取最大值作为当前持有时的状态 dp[nowday][restTime][1]       

        状态转移公式： 

        dp[i][j][1]=Max(dp[i−1][j][1],dp[i−1][j+1][0]−price[i])" role="presentation">dp[i][j][1]=Max(dp[i−1][j][1],dp[i−1][j+1][0]−price[i])$dp[i][j][1]=Max(dp[i-1][j][1],dp[i-1][j+1][0]-price[i])$

三、代码实现

import java.util.*;
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int maxProfit (int[] prices, int k) {
        // 使用动态规划解决此问题
        int nsize=prices.length;
        if(nsize==0){
            return 0;
        }
        //先看有哪几个可变参数：
        //当前第几天 nowday(范围：0->n-1)
        //剩余交易次数 restTime(范围：k->0)
        //当天可买入还是可卖出 isnowHold(0表示未持有可买入，1表示持有可卖出)
        //初始化三维dp数组
        int[][][] dpArr=new int[nsize][k+1][2];
        for(int i=0;i
            //初始情况下第一天买入持有股票，盈利均为负值
            dpArr[0][i][1]=-prices[0];
        }
        //剩余k次的时候，盈利均为0；第1天就买入的情况上面已经初始化完成
        //所以下面外层天数循环从第二天开始，内层次数循环从k-1次开始
        for(int nowday=1;nowday
            for(int restTime=k-1;restTime>=0;restTime--){
                //要使第nowday天未持有股票，如果前一天未持有则直接迁移过来，如果前一天持有股票则需要卖出
                dpArr[nowday][restTime][0]=Math.max(dpArr[nowday-1][restTime][0],dpArr[nowday-1][restTime][1]+prices[nowday]);
                //要使第nowday天持有股票，如果前一天持有则直接迁移，如果前一天没有，则需要买入
                dpArr[nowday][restTime][1]=Math.max(dpArr[nowday-1][restTime][1],dpArr[nowday-1][restTime+1][0]-prices[nowday]);
            }
        }
        
        return dpArr[nsize-1][0][0];
    }
}

四、刷题链接

买卖股票的最好时机(四)_牛客题霸_牛客网