代码随想录——第四十一天

第九章 动态规划part08

股票问题是一个动态规划的系列问题，前两题并不难，第三题有难度。

121. 买卖股票的最佳时机

视频讲解：https://www.bilibili.com/video/BV1Xe4y1u77q

https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html

class Solution {

    public int maxProfit(int[] prices) {

        int[] res = new int[prices.length -1];

        for(int i = 1; i < prices.length; i ++){

            res[i -1] = prices[i] - prices[i - 1];

        }

        int max = 0;

        int index = 0;

        for(int j = 0; j < prices.length - 1; j ++){

            if(res[j] > 0){

                index = j;

                max = res[j];

                break;

            }

        }

        int sum = 0;

        for(int k = index; k < prices.length - 1; k ++){

            sum += res[k];

            if(sum > max) max = sum;

        }

        return max;

    }

}

首先 if里的break没考虑到 其次没考虑到可能不是从第一个正值开始计算的

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

视频讲解：https://www.bilibili.com/video/BV1D24y1Q7Ls

https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html 

class Solution {

    public int maxProfit(int[] prices) {

        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-1][0] + prices[i]);

        }

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

    }

}

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

这道题一下子就难度上来了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

视频讲解：https://www.bilibili.com/video/BV1WG411K7AR

https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html

class Solution {

    public int maxProfit(int[] prices) {

        int[][] dp = new int[prices.length][4];

        dp[0][0] =  - prices[0];

        dp[0][1] = 0; //持有

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

        dp[0][3] = 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-1][0] + prices[i]);

            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]-prices[i]);

            dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]);

        }

        return dp[prices.length -1][3];

    }

}