python 买卖股票的最佳时机 LeetCode No.122

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 = 0for 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 = 0for i in range(1,len(prices)):if prices[i-1]<prices[i]:money+=prices[i]-prices[i-1]return money