代码随想录第五十天

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

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

题目链接: 买卖股票的最佳时机 III
自己的思路:想不到!!!!高维dp数组!!

正确思路:这里和之前的都不太一样,因为限制了买卖股票的次数,所以我们就加大dp数组的维度;动规五部曲:1、dp数组的含义:dp[i][0]表示一开始不操作的情况、dp[i][1]表示第一次持有(不一定第i天才买入)、dp[i][2]表示第一次不持有(不一定第i天才卖出)、dp[i][3]表示第二次持有(不一定第i天才买入)、dp[i][4]表示第二次不持有(不一定第i天才卖出);2、递推公式:其实和上一题的递推公式是一样的;拿一种情况来讨论:dp[i][3]的情况:(1)、当第i天不买入的时候:dp[i-1][3];(2)、当第i天买入的时候:dp[i-1][[2]-prices[i];取最大值,其他的情况类似,不做讨论!3、dp数组初始化:由于后面的都是由dp[0][:]的时候推导得到,所以我们初始化dp[0][:],dp[0][0]=0因为一开始的金额是0;dp[0][1]=-prices[0]因为一开始金额为0,买入之后金额变成负的prices[0];dp[0][2]=0这里可以看做是第一天买入又卖出;dp[0][3]这里可以看做是第一天买入又卖出又买入;dp[0][4]这里可以看做是第一天买入又卖出又买入又卖出!!!4、遍历顺序:还是和之前一样从前向后遍历;5、打印dp数组:主要用于debug!!!!

代码:文章来源地址https://www.toymoban.com/news/detail-679446.html

class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        int[][] dp = new int[length][4];
        //dp数组初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 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][1],dp[i][0]+prices[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i][1]-prices[i]);
            dp[i][3] = Math.max(dp[i-1][3],dp[i][2]+prices[i]);
        }
        return dp[length-1][3];
    }
}

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

题目链接: 买卖股票的最佳时机 IV
自己的思路:其实和上一题基本一样,只不过广义化了一下,注意点细节就可以!!!!!

代码:

class Solution {
    public int maxProfit(int k, int[] prices) {
        int length = prices.length;
        int[][] dp = new int[length][2*k+1];
        //dp数组初始化
        for (int i=0;i<=2*k;i++){
            if (i%2==0) dp[0][i] = 0;
            else dp[0][i] = -prices[0];
        }
        for (int i =1;i<prices.length;i++){
            //递推公式
            for (int j=1;j<=2*k;j++){
                if (j%2==0) dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
                else dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
            }
        }
        return dp[length-1][2*k];
    }
}

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

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

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

相关文章

  • 代码随想录第五十七天|● 392.判断子序列 ● 115.不同的子序列

    题目: 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,而\\\"aec\\\"不是)。 进阶: 如果有大量输入的 S,称作 S1, S2, … , Sk 其中

    2024年02月06日
    浏览(48)
  • 代码随想录——贪心算法

    代码随想录——回溯 代码随想录——贪心算法 分发饼干 链接:https://leetcode.cn/problems/assign-cookies/description/ 这道题我自己一开始的想法是从大到小遍历孩子数组,对于每个元素从大到小遍历饼干数组,满足则total+1,并且该元素置0防止被再次使用。这样虽然是可以的,但时间复

    2024年02月22日
    浏览(57)
  • 第10天-代码随想录刷题训练-第五章 栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈

    栈和队列对应的三个不同的STL版本,底层实现方式不一样, 为我们所知道的是 SGI STL 栈 栈提供 pop和push等接口, 不提供走访功能 也不提供迭代器, 不像map和set可以使用迭代器遍历,往往不被归类为容器,而是容器适配器 栈的内部实现结构可以使用 verctor、list 和 deque(默认)

    2024年02月04日
    浏览(41)
  • 代码随想录day24 开启回溯算法

    感觉回溯算法其实和递归很像,也是用递归的做法,也有三部曲,但又不太一样的地方是递归中类似二叉树,只有纵向遍历(一层层往下遍历,没有横向遍历),而回溯算法中多的for循环就是横向遍历,说实话这一点我没有理解的太深,只是知道它类似于两个for循环中的第一

    2024年01月16日
    浏览(53)
  • 代码随想录day31 贪心算法初探

            就像卡哥视频里说的一样,感觉贪心算法确实没什么固定的套路,唯一的思路就是求局部最优解然后推广到全局最优解,但是什么是局部最优解,这个需要慢慢做题来摸索总结,有点像调参,蛮玄学的,纯考脑子 假设你是一位很棒的家长,想要给你的孩子们一些

    2024年01月18日
    浏览(179)
  • 代码随想录算法训练day4 | 链表

    目录 24. 两两交换链表节点 19. 删除链表倒数第n个节点 方法一:普通写法 方法二:双指针法 面试题:找链表相交节点 142. 判断环形链表 虚拟头节点的本质意义在于减少了特殊情况的处理。不用判断该节点是否在链表的第一位。 定义快慢两个指针。 fast先走n步,再让fast和s

    2024年02月04日
    浏览(67)
  • 代码随想录-回溯算法(子集问题)|ACM模式

    目录 前言: 78. 子集 题目描述: 输入输出描述: 思路和想法: 90. 子集 II 题目描述: 输入输出描述: 思路和想法: 491. 递增子序列 题目描述: 输入输出描述: 思路和想法: 如果把 子集问题、组合问题、分割问题都抽象为一棵树的话, 那么组合问题和分割问题都是收集

    2024年02月15日
    浏览(155)
  • 代码随想录-回溯算法(分割问题)|ACM模式

    目录 前言: 131. 分割回文串 题目描述: 输入输出描述: 思路和想法: 93. 复原 IP 地址 题目描述: 输入输出描述: 思路和想法:          回溯算法中的分割问题,是可以抽象为组合问题的,其中模拟切割线、切割问题中递归如何终止以及递归循环中如何截取子串,是我们

    2024年02月15日
    浏览(55)
  • 代码随想录算法训练DAY25|回溯2

    力扣题目链接 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]

    2024年01月22日
    浏览(62)
  • 代码随想录算法训练DAY27|回溯3

    力扣题目链接 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明: 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。 示例 1: 输入:candidates = [2,3,6,

    2024年01月23日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包