以下為我的天梯積分規則：
每日至少一題：一題積分+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??哈哈哈哈
?創作不易?，過路能?關注、收藏、點個贊?三連就最好不過了
?( ′･?･` )
?
『
命運負責洗牌和發牌，而我們只能出牌，
』
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/333804.html
標籤：python
下一篇：Python中的條件陳述句