1.思路：max[k] = k.val+max(max(k.left),max(k.right)) 注意缓存，避免重复计算

image.png

2.母牛生小牛问题

image.png

递推计算思路：
C(n) = 2*C(n-1)-未满4年的母牛数量

现在计算未满4年的母牛数量：分别记3年的，2年的和1年的为K3n,K2n,K1n,
那么递推公式为：
K3n = K2n-1 去年两岁的牛今年都三岁了
K2n = K1n-1 去年一岁的牛今年都两岁了
K1n = C(n-1) - C(n-2) 去年新出生的牛今年都一岁了（去年的牛总数减去千年的牛总数即为去年新出生的牛）

带入计算未满4年的母牛数量：
1岁牛+2岁牛+3岁牛：
C(n-1)-C(n-2) + C(n-2) - C(n-3) + C(n-3) - C(n-4) = C(n-1) - C(n-4)

所以最终地推公式为：
C(n) = 2*C(n-1) - C(n-1) + C(n-4) = C(n-1) + C(n-4)

注意缓存，不要死计算斐波拉契。。

3