买卖股票系列(力扣121、122、123、188、309、714) Java动态规划

简介: 使用两个变量,一个变量max来保存截止到当天获得的最大利润,另一个变量min来保存截止到当天股票的最小价格,动态规划即可求出所有的当天价格中,最大的价格

一、买卖股票的最佳时机(力扣121)



121. 买卖股票的最佳时机-力扣


使用两个变量,一个变量max来保存截止到当天获得的最大利润,另一个变量min来保存截止到当天股票的最小价格,动态规划即可求出所有的当天价格中,最大的价格

class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0];    //截止到当天,股票的最小价格
        int max = 0;            //截止到当天,买卖股票能获得的最佳利润
        for(int i=1; i<prices.length; i++) {            
            max = Math.max(max, (prices[i]-min));
            min = Math.min(min, prices[i]);
        }
        return max;
    }
}


二、买卖股票的最佳时机 II(力扣122)



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


2.1 贪心


等价于每天都交易,只要是赚钱的就卖。(比如股票价格为2,3,4。2块钱买进,4块钱卖出 等价于 2块钱买3块钱卖,3块钱买4块钱卖)

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;    //利润总和
        for(int i=1; i<prices.length; i++) {
            int temp = prices[i]-prices[i-1];
            if(temp > 0) {  //如果是赚钱的就卖
                res += temp;
            }
        }
        return res;
    }
}


2.2 动态规划

和下面的三一样的思路 :

class Solution {
    public int maxProfit(int[] prices) {
        int a = 0 - prices[0];  //持有股票的状态
        int b = 0;              //不持有股票的状态
        for(int i=0; i<prices.length; i++) {
            int temp = a;
            a = Math.max(a, b-prices[i]);
            b = Math.max(b, a+prices[i]);
        }
        return b;
    }
}


三、最佳买卖股票时机含冷冻期(力扣309)



309. 最佳买卖股票时机含冷冻期-力扣


3.1 动态规划


一天有三种状态:持有股票、处于冷冻期、无股票也不在冷冻期

       我们使用dp[i][]数组来表示第i天各种状态下的最大利润,

  • dp[i][0]        表示持有股票
  • dp[i][1]        表示不持有股票,在冷冻期(表示当天结束后处于冷冻期,即当天卖出了股票)
  • dp[i][2]        表示不持有股票,不在冷冻期


那么,dp[i][0]的值取决于:因为当天持有股票,那么有两种情况:1、是之前一直持有的,此时i-1天必须持有股票,则值为dp[i-1][0];2、是当天刚买的,那么前一天不能持有股票,也不能再冷冻期,只可能是2状态,再扣去买股票的钱,则值为dp[i-1][2] - prices[i]。则:


dp[i][0] = max{ dp[i-1][0] , dp[i-1][2] - prices[i] }


dp[i][1]的值取决于:因为dp[i][1]表示当天结束后处于冷冻期,即当天卖出了股票,则前一天必须持有股票,那么只要一种情况,即 dp[i-1] + prices[i]


dp[i][2]的值取决于:因为当天既不持有股票,也不在冷冻期,说明前一天不持有股票,可能在冷冻期也可能不在,那么有两种情况:1、前一天在冷冻期,那么当天值为dp[i-1][1];2、前一天不在冷冻期,那么当天值为dp[i-1][2]。则:


dp[i][2] = max{ dp[i-1][1] , dp[i-1][2] }

     

那么我们所求的是什么值呢?因为要想利润最大,最后一天必然不可能持有股票,所以我们要求的是    max{ dp[len-1][1] , dp[len-1][2] }

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


3.2 优化空间

     

其实当天的状态只与前一天有关,那么我们只用变量保存即可。

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int a = 0 - prices[0];
        int b = 0;
        int c = 0;
        for(int i=1; i<len; i++) {
            int tempA = a;
            int tempB = b;
            int tempC = c;
            a = Math.max(tempA, (tempC-prices[i]));
            b = tempA + prices[i];
            c = Math.max(tempB, tempC);
        }
        return Math.max(b, c);
    }
}


四、买卖股票的最佳时机含手续费 (力扣714)



714. 买卖股票的最佳时机含手续费-力扣

     

因为每次交易有手续费,就不能像2.1那样做了,但是2.2的做法是通用做法,只要在卖出股票的时候把手续费减掉就行。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int a = 0 - prices[0];  //持有股票的状态
        int b = 0;              //不持有股票的状态
        for(int i=0; i<prices.length; i++) {
            int temp = a;
            a = Math.max(a, b-prices[i]);
            b = Math.max(b, a+prices[i]-fee);
        }
        return b;
    }
}


相关文章
|
1月前
|
算法 Java
LeetCode(一)Java
LeetCode(一)Java
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
50 6
|
3月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
68 2
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
50 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
59 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
79 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
39 0
|
3月前
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
36 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
44 0