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
