122. 买卖股票的最佳时机 II
贪心选择：
贪心算法基于这样的事实：从第i天买入股票，到第j天(j > i)出售，所获得的利润profit[i, j] = prices[j] - prices[i] = (prices[j] - prices[j - 1]) + (prices[j - 1] - prices[j - 2]) + ... + (prices[i + 1] - prices[i])，也就是说，由于同时只能持有一份股票，要取得最大的收益，就要每天选择是否买卖股票，使用贪心算法也就很好理解：问题是具有最优子结构的，因为每两天选择是否买卖会剩下一个子问题，一次贪心选择只剩一个同样的子问题，每一次都做贪心选择可以得到最终最优解。
代码就一行：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return sum(prices[i] - prices[i - 1] if prices[i] > prices[i - 1] else 0 for i in range(1,len(prices)))动态规划：
dp[i][0]表示第i天结束时，手上不持有股票的最大利润。dp[i][1]表示第i天结束时，手上持有股票的最大利润。
可以多次交易的情况，状态转移方程如下：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])：表示今天手上没有股票，可能是从昨天就没有，或者是今天卖出了。dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])：表示今天手上有股票，可能是从昨天就持有，或者是今天买入的。因为允许多次交易，就是昨天没持有股票的最大利润（累计起来的）-prices[i]。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0] * 2 for _ in range(n)]
dp[0][0], dp[0][1] = 0, -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return max(dp[n - 1][0], dp[n - 1][1])55. 跳跃游戏
贪心选择，每一步都取目前为止最长的可覆盖距离。
自己写的有点冗长，思路不是很清晰，直接给出修改版：
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
n = len(nums)
for i,num in enumerate(nums):
if farthest < i:
return False
farthest = max(num + i, farthest)
if farthest >= n - 1:
return True
return False我在处理边界条件的时候遇到一些问题，这种写法可以巧妙地把边界条件涵盖进循环。具体边界条件包括：刚好到达末尾元素前一个位置；数组只有一个元素。问题主要是python不支持动态修改for循环中的变量。
可以改成while循环, 思路更清晰：
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
n = len(nums)
i = 0
while i <= farthest:
farthest = max(farthest, nums[i] + i)
if farthest >= n - 1: return True
i += 1
return False45. 跳跃游戏 II
自己的思路：
自己前几天写的时候写成了一个最差情况O(n^2)的算法，好歹能AC：
class Solution:
def jump(self, nums: List[int]) -> int:
farthest = [num + i for i,num in enumerate(nums[:-1])]
step = 0
s = len(nums)
target = s - 1
while target > 0:
for i, _ in enumerate(farthest):
if _ >= target:
step += 1
target = i
break
return step主要思路就是从末端开始，找第一个能到target的位置，然后把这个位置更新成target，自然也就是跳了一步。感觉也算是一种贪心算法，因为每次都找第一个能跳到target的地方，保证跳的最远。这种方法复杂度稍高是因为精确的找到了跳哪里，但是题目只需要求最小次数，对从哪跳到哪并不关心。
优化的方法：宝宝你是一个超人！
这里完成了题解的方法二，这种方法其实挺难理解的，因为他不是模拟跳跃过程，而是从贪心选择的角度找起跳后的落点。初始化steps其实是起跳次数，初始化落点选在了第一个位置但没有起跳，当然，如果len(nums) == 1，不会经过循环，直接return了初始化的steps。
对于一般情况，实际上是起跳后对数组里每一个数做一次贪心选择，落还是不落，如果i < end，贪心选择不落下来，而是找farthest，在i==end的时候，这时候实际上是选择落到能达到当前farthest的点（这个点其实并不需要知道具体在哪里）落下随后再次起跳。
所以对于代码随想录中的题解，可以这样解释过程：
你是一个超人并且理解你一定能用某种方法落到终点，初始你落到了起点，落下前你也观测到了从起点最远可到的位置(farthest=nums[0])，你从起始点开始起跳，起跳后跳跃次数加一，但你并没有落地，而是记录了下一个必须落地的位置(end = farthest)并且在空中不断审视之后的情况，你不断记录区间内（end及之前）可以跳到更远的距离farthest，当你在到达end必须下落时拿定了主意，落到可以到farthest的位置再次起跳（因为你是超人，不需要记录具体位置就可以精准落到产生farthest的地方），这时你把end更新成记录好的farthest，然后继续在空中观测farthest，如此循环直到nums[-2]，你知道不需要继续观察，直接落地即可。
对于方法一，需要处理特殊情况，即：
当你发现起点就是终点，不需要跳跃，不去循环里起跳；为了避免end刚好在nums[-1]造成多起跳一次的情况，当你起跳时需要观察新的end是否超过了终点，如果超过了直接落到终点即可。
class Solution:
def jump(self, nums: List[int]) -> int:
farthest, steps, end = 0, 0, 0
i = 0
n = len(nums)
for i, num in enumerate(nums[:-1]):
farthest = max(farthest, num + i)
if i == end:
steps += 1
end = farthest
return steps 今日总结：
前两个题还行，第三个题没有能想到On的算法，看了题解之后虽然自己写错误百出，但是最后完全能够理解代码的思路了，可以用一个形象的解释来说明这个贪心算法。
