代码编织梦想

题意理解

        给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

        返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

        

        注意:这里只有一只股票,只进行一次买卖,求最大利益。

        所以:对于每一天,都有两个状态:持有股票、不持有股票

        这里定义一个二维dp数组:dp[0]表示持有股票能获得的最大收益,dp[0]表示不持有股票能获得最大大受益。

        对于不持有股票的状态:包含当天卖出

        持有股票状态:包含当前买入

解题思路

        定义二维dp[]数组:

        dp[i][0]:表示持有股票能获得的最大收益

        dp[i][1]:表示不持有股票能获得最大大受益

        1.初始化

        dp[0][0]=-price[0];//买入所以当前收益为负

        dp[0][1]=0;//无交易,无收益

        2.递推公式

        dp[i][0]=max(之前买入,当前买入)=max(dp[i-1][0],-prices[i])

        dp[i][1]=max(之前卖出,今天卖出)=max(dp[i-1][1],dp[i-1][0]+prices[i])

1.解题

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],-1*prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);
    }

2.分析

时间复杂度:O(n)

空间复杂度:O(2n)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lt_BeiMo/article/details/136084103

leetcode 77 组合-爱代码爱编程

题意理解:         给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。         如:n=3,k=2,则有:12 13 23         一般,我们使用回溯法来解决组合问题。         组合问题没有顺序要求,所以 12 21 是同一个组合(如果是排列12 21 是两种排列)  

leetcode 216 组合总和 iii-爱代码爱编程

题意理解:         求数字1-9,任取k个数,其和为n的组合         每个数字只能用一遍         这里的求的是组合,即k个值不看顺序。 解题思路:按照回溯法解题模板         1.确定返回值及参数                 List<>results :记录符合条件的结果  

leetcode 406 根据身高重建队列-爱代码爱编程

题意理解:         people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]         给定一个二维数组,(h,k)h表示此人身高,k表示前面有几个人比他高。         我们按照每个人的h,k两个维度的需求给每个人排在合适的位置。         如:            

leetcode98 验证二叉搜索树-爱代码爱编程

题意理解:         首先明确二叉树的定义,对于所有节点,根节点的值大于左子树所有节点的值,小于右子树所有节点的值。 注意一个误区:         根节点简单和左孩子,右孩子比大小是不够的,要和子树比,如下图:        他每个节点根节点大于左孩子,小于右孩子。        但是他的每个根节点不大于左子树的所有节点的

leetcode 236 二叉树的最近公共祖先-爱代码爱编程

题意理解:         二叉树的最近公共祖先: 简单理解,就是p和q值的那两个节点,不断向上返回,然后会在一个点汇合,那么他们第一次汇合的这个点就是他们的最近公共祖先。 解题的思路就是:         如果这一层找到了p或q的值,就向上一层返回。         如果父节点的左右分别找了p、q节点,则返回父节点      

leetcode 763 划分字母区间-爱代码爱编程

题意理解:         要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。         注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。         返回一个表示每个字符串片段的长度的列表。         输入:s = "ababc bacad efeg"         输出

leetcode 746 使用最小花费爬楼梯-爱代码爱编程

题意理解:         给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。         一旦你支付此费用,即可选择向上爬一个或者两个台阶。         你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯         目标:使用最小的花费到达楼梯顶部。         例

leetcode 968 监控二叉树-爱代码爱编程

理解题意:         给定一个二叉树,我们在树的节点上安装摄像头。         节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。         计算监控树的所有节点所需的最小摄像头数量。         什么是监控?                  目标:最少的摄像头数目监控所有节点。 解题思路:

leetcode 17 电话号码的字母组合-爱代码爱编程

理解题意:         给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合                 本质上:数字代表着一个字母集合                 数字的个数决定了递归的深度,即树的深度                 数字代表的字母组合决定了当前树的宽度。         

完全背包总结二-爱代码爱编程

1.完全背包和0/1背包的区别? 完全背包的物体有无限个,可以多次放入 0/1背包的物体只有一个,只能放入一次 2.关于物品遍历顺序 在0/1背包中为了防止物品被重复放入,所以选择倒序遍历背包 而完全背包中,可以重复放入,所以选择正序遍历背包 具体来说,如题目 重量价值物品1115物品2320物品3535 求大小为4的背包可获得的最

背包问题总结_0-爱代码爱编程

1.背包问题是什么?有哪些? 背包问题包含:0-1背包、完全背包、多重背包,还有一些特殊的如:分组背包、混合背包         0-1背包:多种物品,每个物品1个         完全背包:多种物品,每个物品n个         多重背包:多种物品,每个物品不一样多个 最基础的是:0-1背包、完全背包 竞赛类:分组背包、混合背

leetcode 494 目标和-爱代码爱编程

题意理解:         给你一个非负整数数组 nums 和一个整数 target 。         向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。

leetcode 1049 最后一块石头的重量ii-爱代码爱编程

题意理解:         有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。         每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。         思路转化:我们可以将题目转换为,将石头分为大小相等差不多的两堆,然后相

leetcode 518 零钱兑换 ii-爱代码爱编程

题意理解:         给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。         请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。         将coins看作不同重量的背包,然后把要凑成的组合数看作背包容量。         则该问题就