买卖股票的最好时机(四)

1. 当前是第几天day；
2. 还剩下几次交易次数rest；
3. 当前的收益profit；
4. 之前是不是刚卖掉股票notBuy。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    int maximumProfit = 0;
    public int maxProfit (int[] prices, int k) {
        // write code here
        recurrent(prices, 0, k, 0, true);
        return maximumProfit;
    }
    
    private void recurrent(int[] prices, int day, int rest, int profit, boolean notBuy) {
        if(day == prices.length || rest == 0){
            // 来到最后一天或交易数已经用完，结算收益
            maximumProfit = Math.max(maximumProfit, profit);
            return;
        }
        if(notBuy){
            // 还没买过可以买或者不买
            recurrent(prices, day + 1, rest, profit, notBuy);    // 不买
            recurrent(prices, day + 1, rest, profit - prices[day], !notBuy);      // 买
        }else{
            // 当前可以选择卖与不卖
            recurrent(prices, day + 1, rest, profit, notBuy);    // 不卖
            recurrent(prices, day + 1, rest - 1, profit + prices[day], !notBuy);    // 卖
        }
    }
}

1. base case：第一天如果买入股票，则收益为股价的相反数，即dp[x][0][1]=-prices[0]。
2. 分析递归的参数列表：profit是要填入到dp表中的值，因此它不是一个可变的参数，可变参数一共有day，rest，notBuy三个，因此本质上是一个三维动态规划问题。
3. 根据参数的取值范围，确定dp表的维度：day的取值范围是0~n-1，rest的取值范围是0~k，notBuy为布尔类型只有两个取值，这里把它规定为0和1。因此dp表的维度可以规定为(k+1)*n*2。
4. 分析状态转移：暴力递归中的递归调用就对应于动态规划从dp表中取值。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int maxProfit (int[] prices, int k) {
        // write code here
        int n = prices.length;
        if(n == 0) return 0;
        int[][][] dp = new int[k + 1][n][2];
        for(int i = 0; i <= k; i++){
            dp[i][0][1] = -prices[0];     // 首日买入均为负债情况
        }
        for(int day = 1; day < n; day++){
            for(int rest = k - 1; rest >= 0; rest--){
                // 要保证第day天手上无股票，可以在前一天持股的基础上卖掉也可以直接从前一天无股的状态转移过来
                dp[rest][day][0] = Math.max(dp[rest][day - 1][0], dp[rest][day - 1][1] + prices[day]);
                // 要保证第day天手上有股票，可以在前一天无股的基础上买入也可以直接从前一天有股的状态转移过来
                dp[rest][day][1] = Math.max(dp[rest][day - 1][1], dp[rest + 1][day - 1][0] - prices[day]);    // 开启一次新的交易会使得剩余交易数减1
            }
        }
        return dp[0][n - 1][0];
    }
}

动态规划空间压缩

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int maxProfit (int[] prices, int k) {
        // write code here
        int n = prices.length;
        if(n == 0) return 0;
        int[][] dp = new int[k + 1][2];
        for(int i = 0; i <= k; i++){
            dp[i][1] = -prices[0];     // 首日买入均为负债情况
        }
        for(int day = 1; day < n; day++){
            for(int rest = k - 1; rest >= 0; rest--){
                // 要保证第day天手上无股票，可以在前一天持股的基础上卖掉也可以直接从前一天无股的状态转移过来
                dp[rest][0] = Math.max(dp[rest][0], dp[rest][1] + prices[day]);
                // 要保证第day天手上有股票，可以在前一天无股的基础上买入也可以直接从前一天有股的状态转移过来
                dp[rest][1] = Math.max(dp[rest][1], dp[rest + 1][0] - prices[day]);
            }
        }
        // 返回剩余交易数为0，且手中已经没有股票时的利润
        return dp[0][0];
    }
}