贪心5.
这题主要难点是转化问题。
经过我的缜密分析，满足条件的结果可以分为两种情况：
| 最高位数字不变，后面位次是符合题意的最优解，并且两部分合起来仍然是符合题意的。比如1234=>1 | 234，234是234的最优解，并且2>=1，所以合起来仍是最优解。 |
所以递归很容易就看出来了吧。
def monotoneIncreasingDigits(self, n: int) -> int:
def maxMonotoneNumber(s):
if len(s) == 1:
return s
# 情况1
backup = str(int(s[0])-1)
for _ in range(len(s)-1):
backup += "9"
# 情况2（子问题）
sub = maxMonotoneNumber(s[1:])
if sub[0] < s[0]:
return backup
return s[0]+sub
return int(maxMonotoneNumber(str(n)))
如果说122. 买卖股票的最佳时机 II是看到单调递增区间就allin，那么这题就更为复杂。反正我是没想出来贪心怎么做。
贪心思路可以这么理解：
如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。
此时无非就是要找到两个点，买入日期，和卖出日期。
所以我们在做收获利润操作的时候其实有三种情况：
这题看看就好，DP才是常规做法。
def maxProfit(self, prices: List[int], fee: int) -> int:
result = 0
minPrice = prices[0]
for i in range(1, len(prices)):
# 情况二
if prices[i] < minPrice:
minPrice = prices[i]
# 情况三
elif prices[i] >= minPrice and prices[i] <= minPrice + fee:
continue
else:
# 情况一
result += prices[i] - minPrice - fee
minPrice = prices[i] - fee
return result
贪心最后一题来个hard。
这题最直接的想法是用递归来做，用前序遍历，对于每一个经过的节点，维持一个invariant：递归遍历过之后root必须被监控到（或者root中含有摄像头）。不过就算加了memoization还是超时了。。
def minCameraCover(self, root: TreeNode) -> int:
memo = {}
# invariant: root should be covered after calling helper(root, T/F)
def helper(root, covered, rootCam=False):
if not root:
return 0
if (root, covered, rootCam) in memo:
return memo[(root, covered, rootCam)]
res = 0
if covered:
if rootCam: # 下面的a情况
res = helper(root.left, True) + helper(root.right, True)
else: #下面的c情况
noroot = helper(root.left, False) + helper(root.right, False)
root = 1 + helper(root.left, True) + helper(root.right, True)
res = min(root, noroot)
else: #下面的b情况
left = 1 + helper(root.left, True, True)+helper(root.right, False) if root.left else inf
right = 1 + helper(root.left, False)+helper(root.right, True, True) if root.right else inf
root = 1 + helper(root.left, True)+helper(root.right, True)
res = min(left, # root camera
right, # left camera
root) # right camera
memo[(root, covered, rootCam)] = res
return res
return helper(root, False)
看了题解，这题要过还是用DP。实际上想法和之前我的解法很像。
为什么要设这三个状态呢？因为root要被监控到，有三种情况：1.root自己放摄像头(a)。2. root没被父亲监控，但被孩子监控(b)。3. root被父亲监控，孩子监不监控无所谓(c)。
所以
base case：如果root为空，则root上不可能放摄像头。根据语义，返回[inf, 0, 0]。
返回值：b。
不难写出如下代码：
def minCameraCover(self, root: TreeNode) -> int:
def dfs(root: TreeNode) -> List[int]:
if not root:
return [float("inf"), 0, 0]
la, lb, lc = dfs(root.left)
ra, rb, rc = dfs(root.right)
a = lc + rc + 1
b = min(a, la + rb, ra + lb)
c = min(a, lb + rb)
return [a, b, c]
a, b, c = dfs(root)
return b
至于还有一种贪心解法，我只能说想不到，也无所谓了。