以下为我的天梯积分规则：
每日至少一题：一题积分+10分
若多做了一题，则当日积分+20分（+10+10）
若做了三道以上，则从第三题开始算+20分（如：做了三道题则积分-10+10+20=40；做了四道题则积分–10+10+20+20=60）
初始分为100分
若差一天没做题，则扣积分-10分（周六、周日除外注：休息）
坚持！！！
初级算法
刷题目录
数组
题干
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
接着上一篇Blog：＜LeetCode天梯＞Day002 买卖股票的最佳时机 II | 初级算法 | Python
动态规划法
第一步：定义状态
定义 dp[ i ][ j ] 为：
其中 dp[ i ][ j ] 表示到下标为 i 的这一天，持股状态为 j 时，我们手上拥有的最大现金数。
注意：限定持股状态为 j 是为了方便推导状态转移方程，这样的做法满足无后效性。
其中：
- 第一维 i 表示下标为 i 的那一天（ 具有前缀性质，即考虑了之前天数的交易 ）；
- 第二维 j 表示下标为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）。
第二步：状态转移方程
- 状态从持有现金（cash）开始，到最后一天我们关心的状态依然是持有现金（cash）；
- 每一天状态可以转移，也可以不动。状态转移用下图表示：
第三步：确定初始值
从一开始：
- 若不做操作，则 dp[0][0] = 0；
- 如果持有股票，当前拥有的现金数是当天股价的相反数，即 dp[0][1] = -prices[i]；
第四步：确定最终值
当我们计算到最后一天的时候，由此可知，
- 输出 dp[len - 1][0]，因为一定有 dp[len - 1][0] > dp[len - 1][1]
class Solution:
def maxProfitByDP(self, prices):
n = len(prices)
if n < 2:
return 0
dp = [0]*n
print(dp)
dp[0] = prices[0] # 将prices的第一天的价格赋给dp[0]
maxValue = 0 # 当前最多能赚多少钱
maxProfit = 0 # 最终的总最大收益
for i in range(1, n):
dp[i] = min(dp[i-1], prices[i]) # 更新当前最低价格
if prices[i] - dp[i] < maxValue:
maxProfit += maxValue
dp[i] = prices[i]
maxValue = 0
else:
maxValue = prices[i] - dp[i]
maxProfit += maxValue
return maxProfit
虽然动态规划法没有贪婪算法的快，但还是很不错的。
Reference
-
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
来源：力扣（LeetCode） -
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/
今日得分：+10
总得分：130（更新算法方法-2021.10.22加10分）加油！！！
?坚持读Paper，坚持做笔记，坚持学习?！！！
再加个坚持刷题！！！打天梯！！！
?To Be No.1??哈哈哈哈
?创作不易?，过路能?关注、收藏、点个赞?三连就最好不过了
?( ′･?･` )
?
『
命运负责洗牌和发牌，而我们只能出牌。
』