讨论/求职面试/面试题|面试题一例,面试官说用动态规划求解,实在没想明白。/
面试题|面试题一例,面试官说用动态规划求解,实在没想明白。

数组里有值为小于n的数组成,找出包含所有0~n-1个数的最小区间。例如:
array = [1,2,0,0,1,2,3,4,1]
n = 5

1

咱不知道你所谓的面试官说的“动态规划”是从哪个角度进行规划,反正不可能是简单的区间dp,那比暴力还慢的做法好意思自称“规划”吗

如果n很小的情况下,比如小于64,那倒可以进行状态压缩的区间dp,虽说也就跟暴力一个速度
(这里说的暴力是指枚举左边界,固定好之后,向右推动右边界,枚举所有区间,时间复杂度O(n2))

展开全部 13 讨论