邯郸网站优化公司,安徽建设工程信息网官网入口,大学生ppt自我介绍幻灯片,网站建设环境软件有哪些题目要求如上#xff0c;这里可以有两种解题思路#xff0c;一种是利用动态规划去求解#xff0c;一种是用贪心去求解。 首先看下动态规划的方法。
用动归去解决
动态规划最重要的就是要想出来递推公式#xff08;这个真的很难#xff09;#xff0c;但是一旦想清楚递推… 题目要求如上这里可以有两种解题思路一种是利用动态规划去求解一种是用贪心去求解。 首先看下动态规划的方法。
用动归去解决
动态规划最重要的就是要想出来递推公式这个真的很难但是一旦想清楚递推公式写代码就很轻松其实感觉这里的算法题都是这种主要考察的是思路而不是工程能力。 首先我们观察题目发现这里说明了每天最多只能持有一只股票因此这里的每天的状态只有两种
不持有股票持有股票
那我们最后只有返回两种状态下的最大利润就可以了有时候想不明白可以先想3天的情况会更好推理。我们定义 d p [ i ] [ 0 ] dp[i][0] dp[i][0] 表示第i天不持有股票所获得的最大利润 d o [ i ] [ 1 ] do[i][1] do[i][1] 表示第i天持有股票所获得的最大利润
先来看不持有股票的情况
前一天持有股票但今天卖出了此时截止今天的最大收益为dp[i-1][1] prices[i]前一天没有持有股票而且今天也不买此时截止今天的最大收益为dp[i-1][0]
因此对于没有持有股票来说递推公式为 d p [ i ] [ 0 ] m a x ( d p [ i − 1 ] [ 1 ] p r i c e s [ i ] , d p [ i − 1 ] [ 0 ] ) dp[i][0] max(dp[i-1][1] prices[i], dp[i-1][0]) dp[i][0]max(dp[i−1][1]prices[i],dp[i−1][0]) 再来看持有股票的情况
前一天持有股票今天也不能买了此时截止今天的最大收益为dp[i-1][1]前一天没有持有股票今天买入股票此时截止今天的最大收益为dp[i-1][0] - prices[i]
因此对于没有持有股票来说递推公式为 d p [ i ] [ 1 ] m a x ( d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] , d p [ i − 1 ] [ 1 ] ) dp[i][1] max(dp[i-1][0] - prices[i], dp[i-1][1]) dp[i][1]max(dp[i−1][0]−prices[i],dp[i−1][1]) 对于初始状态 d p [ 0 ] [ 0 ] 0 , d p [ 0 ] [ 1 ] − p r i c e s [ 0 ] dp[0][0]0, dp[0][1]-prices[0] dp[0][0]0,dp[0][1]−prices[0] 有了初始状态和递推公式代码岂不是手到擒来
def solve(prices):days len(prices)if days 0:return 0rst [[0, 0]] * daysrst[0][0] 0 # 第i天不持有股票能获得的利益rst[0][1] -prices[0] # 第i天持有股票能获得的利益for i in range(1, days):rst[i][0] max(rst[i - 1][0], rst[i - 1][1] prices[i])rst[i][1] max(rst[i - 1][1], rst[i - 1][0] - prices[i])return max(rst[-1])贪心思路
真的觉得贪心就是脑筋急转弯。贪心思路很好理解但是一般很难想到。 既然我的目的是计算出最大收益那我只要保证我每天的收益都是最大的就可以了。那我怎么保证呢只要我每天的收益都是正的那就是最大收益咯。 r s t r s t m a x ( 0 , p [ i ] − p [ i − 1 ] ) rst rst max(0, p[i]-p[i-1]) rstrstmax(0,p[i]−p[i−1])
代码也超简单
def greed_solve(prices):rst 0for i in range(1, len(prices)):rst max(0, prices[i] - prices[i - 1])return rst
