首页 > 编程学习 > Day 50 | 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV

今天还好。。因为是昨天的延续,比昨天顺利多了。。起码能看懂代码。。也自己推导了一遍,写出来了代码。

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

动态规划解题思路:

dp数组的定义:

        本题与股票II的区别在于:只可以最多买卖两次。

        因此一天有五种状态:

0.无操作  1.第一次买  2.第一次卖  3.第二次买  4.第二次卖

dp[i][1/3]代表买入股票的最大钱数,dp[i][2/4]代表卖出股票的最大钱数,赋值规则与股票II相同。

初始化:

        dp[0][0]没有操作一直为0,dp[0][2],dp[0][4]是卖出操作,一定是收获利润,此时没有利润,第一天也不可能进行卖出操作,因此初始化为0.

        dp[0][1]为第一次买入,即-price[0],dp[0][3]:当前手头上没有现金只要买入现金就减少,因此为-price[0]。

    public static int maxProfit(int[] prices) {
        int[][] dp=new int[prices.length][5];
        dp[0][1]=-prices[0];
        dp[0][3]=-prices[0];
        for (int i=1;i<prices.length;i++){
            dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
            dp[i][3]=Math.max(dp[i-1][2]-prices[i],dp[i-1][3]);
            dp[i][2]=Math.max(dp[i-1][1]+prices[i],dp[i-1][2]);
            dp[i][4]=Math.max(dp[i-1][3]+prices[i],dp[i-1][4]);
        }
        return dp[prices.length-1][4];
    }

188. 买卖股票的最佳时机 IV

动态规划解题思路:

        本题与III的区别就是买卖次数的变化,可以观察到对于交易k次,dp[i][j],j共有2*k+1种状态,且i=偶数状态下都是卖出,i=奇数状态下都是买入,其余与上题相同。

        因此定义dp[price.length][2*k+1]代表第i天,在第2*k+1状态下的股票状态。

        初始化时,对奇数个代表买入状态的元素进行赋值-price[0]即可。

    public static int maxProfit(int k, int[] prices) {
        int[][] dp = new int[prices.length][2 * k + 1];
        for (int i = 1; i <= k; i++) {
            dp[0][2 * i - 1] = -prices[0];
        }
        for (int d = 1; d < prices.length; d++) {
            for (int i = 1; i <= k; i++) {
                dp[d][2 * i - 1] = Math.max(dp[d - 1][2 * i - 2] - prices[d], dp[d - 1][2*i-1]);
                dp[d][i * 2] = Math.max(dp[d - 1][2*i-1] + prices[d], dp[d - 1][i*2]);
            }
        }
        return dp[prices.length - 1][2 * k];
    }

 

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式