LeetCode House Robber III条件递归DFS解法的时间复杂度是多少？

你写的这版无记忆化DFS的时间复杂度是 O(2^N)，你推测的0.5系数属于常数项，在大O复杂度的统计规则中会被忽略，量级判断和你的预期是一致的。

推导依据 #

• 你的dfs函数存在两个可变输入：当前节点指针、robbed_previous布尔状态，单节点最多对应2种不同的计算状态
• 没有加缓存的前提下，同一个节点的同一个状态会被上层递归的不同选择路径重复触发计算：比如上层节点分别走了抢或不抢的分支，都可能触发对同一个子节点的相同robbed_previous状态的递归调用，调用次数会随节点数增长呈指数级上升
• 最坏情况是树退化为单链表，每次遇到robbed_previous == false的调用都会触发子节点的两次递归，累计总调用次数就是2的N次方量级

你可以给每个节点增加状态缓存，分别存储「当前节点父节点被抢时的最大收益」、「当前节点父节点未被抢时的最大收益」两个值，保证每个节点的两个状态只会被计算一次，优化后时间复杂度可以降到O(N)，空间复杂度为O(N)（递归栈+缓存的开销）。

内容的提问来源于stack exchange，提问作者Marlon