代码学习记录39---动态规划

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

随想录日记part39

t i m e : time: time 2024.04.09



主要内容:今天开始要学习动态规划的相关知识了,今天的内容主要涉及:
买卖股票的最佳时机。

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


动态规划五部曲:
【1】.确定dp数组以及下标的含义
【2】.确定递推公式
【3】.dp数组如何初始化
【4】.确定遍历顺序
【5】.举例推导dp数组

Topic1买卖股票的最佳时机

题目:
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票,并选择在 未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

输入: [ 7 , 1 , 5 , 3 , 6 , 4 ] [7,1,5,3,6,4] [7,1,5,3,6,4]
输出: 5 5 5
解释: 在第2天(股票价格=1)的时候买入,在第5天(股票价格=6)的时候卖出,最大利润=6-1= 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

思路:

接下来进行动规五步曲:
1.确定dp数组以及下标的含义:
dp[i]表示i+1天的最大利润;
2.确定递推公式:
if (prices[i] - tem > dp[i - 1]) { dp[i] = prices[i] - tem; } else { dp[i] = dp[i - 1]; if (prices[i] < tem) { tem = prices[i]; } }

3.dp数组如何初始化
dp[0] = 0;
int tem = prices[0];
4.确定遍历顺序
5.举例推导dp数组

代码如下:

class Solution {
    public int maxProfit(int[] prices) {
        int l = prices.length;
        if (l == 1)
            return 0;
        // dp[i]表示i+1天的最大利润;
        int[] dp = new int[l + 1];
        // 初始化
        dp[0] = 0;
        int tem = prices[0];
        for (int i = 1; i < l; i++) {
            if (prices[i] - tem > dp[i - 1]) {
                dp[i] = prices[i] - tem;
            } else {
                dp[i] = dp[i - 1];
                if (prices[i] < tem) {
                    tem = prices[i];
                }
            }
        }
        return dp[l - 1];
    }
}


时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)



Topic2买卖股票的最佳时机II

题目:

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买,然后在同一天出售。返回你能获得的最大利润 。

输入: p r i c e s = [ 7 , 1 , 5 , 3 , 6 , 4 ] prices = [7,1,5,3,6,4] prices=[7,1,5,3,6,4]
输出: 7 7 7
解释:
在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。
思路:

接下来进行动规五步曲:
1.确定dp数组以及下标的含义:
dp[i][0] 表示第i天持有股票所得现金。
dp[i][1] 表示第i天不持有股票所得最多现金
2.确定递推公式:
如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来:

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

再来看看如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来

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

3.dp数组如何初始化
dp[0][0]=-prices[0];
dp[0][1]=0;
4.确定遍历顺序
5.举例推导dp数组

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

时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-861117.html



到了这里,关于代码学习记录39---动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法学习记录:动态规划

    目录 前言: 背景知识: 正文:  什么是动态规划(更新中):  理解动态规划: 状态: 状态转移:  运用动态规划(分析步骤): 例题集(时间顺序)  1.蓝桥OJ 3820:混境之地5(DFS) 2.蓝桥OJ 216:地宫取宝(DFS) 3.蓝桥OJ 1536:数字三角形(迭代法) 4.蓝桥OJ 3367:破损的

    2024年01月25日
    浏览(47)
  • 代码学习记录34---动态规划

    t i m e : time: t im e : 2024.04.02 主要内容 :今天开始要学习动态规划的相关知识了,今天的内容主要涉及两个方面: 背包问题和分割等和子集。 01背包问题 416. 分割等和子集 动态规划五部曲: 【1】.确定dp数组以及下标的含义 【2】.确定递推公式 【3】.dp数组如何初始化 【

    2024年04月10日
    浏览(37)
  • 算法day39|动态规划:不同路径Ⅰ、Ⅱ

    https://leetcode.cn/problems/unique-paths/ 了解下标含义——这里是行列数 理解为什么dfs不能做这道题(超时) https://leetcode.cn/problems/unique-paths-ii/ 初始化时也应该注意限制条件 注意特殊情况的判断

    2024年02月06日
    浏览(49)
  • Day39 代码随想录(1刷) 动态规划 0-1背包

    题目描述 小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间,并且具有不同的价值。  小明的行李空间

    2024年04月23日
    浏览(53)
  • 算法D39 | 动态规划2 | 62.不同路径 63. 不同路径 II

    今天开始逐渐有 dp的感觉了,题目不多,就两个 不同路径,可以好好研究一下 62.不同路径  本题大家掌握动态规划的方法就可以。 数论方法 有点非主流,很难想到。  代码随想录 视频讲解: 动态规划中如何初始化很重要!| LeetCode:62.不同路径_哔哩哔哩_bilibili 这个题看

    2024年04月10日
    浏览(45)
  • 算法训练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日
    浏览(45)
  • 力扣算法刷题Day39|动态规划:不同路径 I&II

    力扣题目:#62.不同路径 刷题时长:参考题解后10min 解题方法:动规 复杂度分析 时间O(m*n) 空间O(m*n) 问题总结 初始化二维数组的python语法:i 对应 m,j 对应n 二维遍历顺序,从上到下从左到右通过两层for循环实现,其中startindex应为1 本题收获 动规思路 确定dp数组及下标的含义

    2024年02月12日
    浏览(52)
  • 【算法】算法学习七:动态规划 | 背包问题 | 最长公共子串(含源代码)

    背包问题是一种经典的组合优化问题,通常有两个版本:0-1背包问题和无限背包问题。 0-1背包问题是指给定一个背包容量和一组物品,每个物品有自己的重量和价值,要求在不超过背包容量的情况下,选择一些物品放入背包,使得物品的总价值最大化。每个物品只能选择放入

    2024年02月09日
    浏览(48)
  • 算法记录 | 48 动态规划

    思路: 1.确定dp数组(dp table)以及下标的含义: dp[i]:前 i 间房屋所能偷窃到的最高金额。 2.确定递推公式: dp[i] = max(dp[i - 2] + nums[i-1], dp[i - 1]) i间房屋的最后一个房子是nums[i−1]。 如果房屋数大于等于 2 间,则偷窃第 i−1 间房屋的时候,就有两种状态: 偷窃第 i−1 间房屋

    2024年02月05日
    浏览(37)
  • 算法记录 | Day53 动态规划

    思路: 本题和动态规划:718. 最长重复子数组 (opens new window)区别在于这里不要求是连续的了,但要有相对顺序,即:“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。 1.确定dp数组(dp table)以及下标的含义 dp[i][j] :长度为[0, i - 1]的字符串text1与长度为[0,

    2024年02月03日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包