算法训练day49|动态规划part10

这篇具有很好参考价值的文章主要介绍了算法训练day49|动态规划part10。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

121. 买卖股票的最佳时机 参考文章:代码随想录

贪心

因为股票就买卖一次,那么贪心的想法很自然就是取最左最小值,取最右最大值,那么得到的差值就是最大利润。

本次重点学习动态规划方法

1. dp数组(dp table)以及下标的含义

dp[i][0] 表示第i天持有股票所得最多现金,一开始现金为负数,所以第一天就持有股票的话,就是为负

dp[i][1] 表示第i天不持有股票所得最多现金

如果按照买入,卖出来分别状态,那什么都不干的状态并不能涵盖

所以应该按照持有,和不持有来区分

持有包含今天买入和之前买入但是这几天一直没变动

不持有包含今天卖出,和之前卖出之后没变动

这两种状态能够涵盖所有情况

2. 递推公式

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • i天买入股票,所得现金就是买入今天的股票后所得现金即:-prices[i]

那么dp[i][0]应该选所得现金最大的,所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1], 也可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
  • i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金即:prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的,dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

3.初始化

由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出

其基础都是要从dp[0][0]和dp[0][1]推导出来,而且在递推过程中只参考前一位,所以有压缩的可能性

那么dp[0][0]表示第0天持有股票,此时的持有股票就一定是买入股票了,因为不可能有前一天推出来,所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票,不持有股票那么现金就是0,所以dp[0][1] = 0;

4.根据递推公式,dp[i]都是由dp[i - 1]推导出来的,那么一定是从前向后遍历

// 解法1
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int length = prices.length;
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[length][2];
        int result = 0;
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[length - 1][1];
    }
}

优化:由于递推公式更新时,只需要参考前一位的数值,所以我们可以将空间压缩为2,滚动更新数组

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int dp[][] = new int[2][2];
        
        dp[0][0] = - prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < len; i++){
            dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], - prices[i]);
            dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
        }
        return dp[(len - 1) % 2][1];
    }
}

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

与上题区别:可以买卖多次股票,但是只能持有一个

只有递归公式有区别

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • i天买入股票,所得现金就是前一天不持有股票的现金,再减去买入今天的股票后花费的现金即:的 dp[i-1][1]-prices[i]

其他均与上题相同

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2, 0));
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }
};

由于只需要用到dp[i-1][0],dp[i-1][1]来推导dp[i][0],dp[i][1]

我们可以把dp数组压缩到 2x2的数组,滚动更新

// 版本二
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(2, vector<int>(2)); // 注意这里只开辟了一个2 * 2大小的二维数组
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
        }
        return dp[(len - 1) % 2][1];
    }
};

本题也可以用贪心方法文章来源地址https://www.toymoban.com/news/detail-767850.html

 // 贪心思路
class Solution {
     public int maxProfit(int[] prices) {
         int result = 0;
         for (int i = 1; i < prices.length; i++) {
             result += Math.max(prices[i] - prices[i - 1], 0);
         }
         return result;
     }
 }

到了这里,关于算法训练day49|动态规划part10的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • day49-动态规划10-买卖股票问题

    但是利用其他思路只能解决具体场景下的问题,并不能解决通用的一些问题。 dp[i][0] :表示第i天持有该股票的最大收益, dp[i][1] 表示第i天不持有该股票的最大收益。需要注意的是第i天的情况是什么样,并不是表示第i天就卖出了这只股票,而是表示 递推公式: dp[i][0] 第一

    2024年02月08日
    浏览(39)
  • day44代码训练|动态规划part06

    完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。 1. dp数组的含义 dp[i][j] 0-i物品,重量为j的容量时,最大的价值 2. 递推公式 dp[i][j] = max(dp[i-1][j],dp[i][j-weight[i]]+value[i]); 两种状态,不用物品i的话,直接是用dp[i-1][j] 选用物品的话,为了重复使用物品i,其实是

    2024年02月03日
    浏览(35)
  • 【代码随想录】Day 49 动态规划10 (买卖股票Ⅰ、Ⅱ)

    https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ dp[i]表示在第i天时,卖/不卖股票能获得的最大利润: 1、卖股票:dp[i] = prices[i] -minPrice(i天以前的最低价格) 2、不卖股票:dp[i] = dp[i-1](因为不卖股票,所以状态和前一天保持一致) ∴dp[i] = max(dp[i-1], prices[i] - minPrice); https

    2024年02月09日
    浏览(41)
  • 代码随想录算法训练51 | 动态规划part12

    本题加了一个冷冻期,状态就多了,有点难度,大家要把各个状态分清,思路才能清晰  视频讲解: 动态规划来决定最佳时机,这次有冷冻期!| LeetCode:309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili 代码随想录 相对122.买卖股票的最佳时机II ,本题只需要在计算卖出操

    2024年01月18日
    浏览(54)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(46)
  • 【Day53】代码随想录之动态规划part10——买卖股票的最佳时机、买卖股票的最佳时机II

    昨天已经把打家劫舍的问题解决了,最后一个题目涉及到树形dp比较难(等到二刷的时候再重点看下),今天的任务是解决股票问题。 今日任务: 121.买卖股票的最佳时机 122.买卖股票的最佳时机II Leetcode题目:【121.买卖股票的最佳时机】 因为此题中买卖股票只能买卖一次。

    2024年03月15日
    浏览(95)
  • java算法day45 | 动态规划part07 ● 70. 爬楼梯 (进阶) ● 322. 零钱兑换 ● 279.完全平方数

    题目描述: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,表示爬到楼顶的方法数

    2024年04月14日
    浏览(54)
  • 算法训练Day39:62.不同路径 63. 不同路径 II 动态规划

    Category Difficulty Likes Dislikes ContestSlug ProblemIndex Score algorithms Medium (67.70%) 1746 0 - - 0 Tags Companies 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

    2023年04月25日
    浏览(44)
  • 算法基础复盘笔记Day10【动态规划】—— 线性DP

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月21日
    浏览(77)
  • Day 47 动态规划 part13

    3道题目 300. 最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组 dp[i]被设置为以nums[i]为结尾的最长递增子序列长度。 思路跟上题一致,甚至还更简单,因为只需要看前一个位置和当前位置的关系就好。 这道题相当于两道第一题重叠考虑,设置dp[i][j]为以i-1为结尾的

    2024年02月07日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包