python 買賣股票的最佳時機 LeetCode No.122
解法：
一、暴力解法
二、貪心算法：由于不限制買賣次數，也沒有交易費用，就可以是用貪心算法。思路：只要第二天比前一天高，我們就買進，第二天賣掉，就可以賺錢。
三、動態規劃：根據算法導論這本最權威的書（最難讀的一本書）中提到動態規劃的四個步驟，第一刻畫一個最優解的結構特征，第二遞歸地定義最優解的值，第三計算最優解的值，通常采用自低向上的方法，第四計算出的信息構造一個最優解（如最長公共子序列中，求出最長的子序列的其中一種組合）想了解的可以看我之前的關于動態規劃的文章資料動態規劃，回到這一題，找到遞推公式是最重要的，也就是第二步，dp[i] = dp[i-1] if prices[i]<=prices[i-1] else dp[i-1]+(prices[i]-prices[i-1])，看起來和貪心算法的思路類似，但是如果加上別的限制條件，貪心算法就不再實用。（ps，下面那個動態規劃的代碼是leetcode上面的，然后我發現，和我自己寫的驚人的相似，哈哈哈笑死了。）
class
Solution
:
def
maxProfit
(
self
,
prices
:
List
[
int
]
)
-
>
int
:
# dp[i] = dp[i-1] if prices[i]<=prices[i-1] else dp[i-1]+(prices[i]-prices[i-1])
res
=
0
for
i
in
range
(
1
,
len
(
prices
)
)
:
if
prices
[
i
]
>
prices
[
i
-
1
]
:
res
+=
(
prices
[
i
]
-
prices
[
i
-
1
]
)
return
res
class
Solution
(
object
)
:
def
maxProfit
(
self
,
prices
)
:
"""
:type prices: List[int]
:rtype: int
"""
money
=
0
for
i
in
range
(
1
,
len
(
prices
)
)
:
if
prices
[
i
-
1
]
<
prices
[
i
]
:
money
+=
prices
[
i
]
-
prices
[
i
-
1
]
return
money
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
