wowowo123

分类

动态规划(1) 未归档(4) 题解(94)

/ 注册

TA的专栏 7篇文章 0人订阅

7篇文章 568人学习

全部文章（共98篇）

leetcode 198 打家劫舍

使用动态规划，看第几间屋子是偷还是不偷，偷的话由之前的没偷的状态转移过来，不偷的话之前可能偷了也可能没偷。 class Solution: def rob(self, nums: List[int]) -> int: dp=[[0,0] for _ in range(...

2021-04-03

0 462

leetcode 64 最小路径和

动态规划的想法，dp数组中存储的位置代表每一条路径到达当前位置的最小路径和，每一个状态进行转移的时候只和左面和上面的位置有关。 class Solution: def minPathSum(self, grid: List[List[int]]) -> int: dp...

2021-04-03

0 472

leetcode 714 股票手续费问题来自专栏

使用动态规划方法，dp数组的状态和之前多次买卖的状态数量一样，一种是天数，一种是持有还是不持有，当股票卖出（买入也可以）需要减去手续费用，注意这个手续费用只能计算一次。 class Solution: def maxProfit(self, prices: List[int], fee: ...

2021-04-02

0 523

leetcode 309 股票买卖冷冻期来自专栏

状态主要分为两种，一种是天数，一种是是否持股以及是否处在冷冻期，这两种状态是复合的，要么持有，要么不持有不冷冻，要么不持有在冷冻。所以设置dp数组，状态转移如下 dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]) d...

2021-04-02

0 533

leetcode 188 股票买卖来自专栏

股票系列问题这样两种方法求解。采用和股票问题3一样的方法，假设股票一天可以多次买卖，因为多次买卖利润为0,所以不会影响结果。注意所有的题都是买和卖其中选择一个算一次操作就可以。 class Solution: def maxProfit(self, k: int, prices: Lis...

2021-04-02

0 568

leetcode 123 股票利润3 来自专栏

动态规划，分析会产生几种状态。哪天的股票，当天是否持有，当天已经买卖过几次,是否持有股票分两种情况，持有还是不持有；已经买卖过几次，分三种，因为题目要求至多2次买卖，分别是0次，1次，2次。也就是组合出来每天有6种情况。然后分别分析这六种情况的状态转移。dp[i][0][0]=dp[i-1][0][...

2021-04-02

0 467

股票利润2 来自专栏

这里同样使用和股票利润1差不多的动态规划方法，由于允许股票多次交易，但不允许股票同时交易，所以每天的状态只能有两个，要么手里有一只股票，要么手里没有股票。通过当天是否有股票，可以由前一天是否有股票推断出，如果当天没有股票的话，可能前一天也没有股票，或者前一天有股票但是今天卖了。如果当天有股票的话，可...

2021-04-02

0 487

leetcode 121 股票利润单调栈解法

由于股票利润本质是在求解当前元素，与之前最小值之间的差值，所以维护一个单调递增的栈，入栈的值都为可能为后面买入股票的历史最低值，当遇到比栈顶元素小的元素证明栈顶元素已经没办法成为后面的最小元素了，所以将栈顶元素与栈底元素进行求差值，最后判断得出最大值。需要注意的是栈内保存的是下标，需要取对应的数组...

2021-04-02

0 594

leetcode 503 下一个最大元素2

这次是循环数组，所以属于一共遍历两次，第一次到了结尾，把i置为0,继续遍历。 class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: result=[-1 for _ i...

2021-03-31

0 496

leetcode 85 最大矩形矩阵

按照矩阵行，每一行为基准线，将矩阵中1的数字看作条形统计图中的柱体，计算最大的矩形。每一行迭代。利用前缀和思想，当当前元素为1，则加上之前的元素，当为0,则清零。计算的柱体面积按照之前最大矩形面积的题目，构造递增单调栈，但遇到比栈顶元素低的元素，就可以计算以栈顶元素高度的面积。 class Sol...

2021-03-31

0 621