动态规划的时间复杂度优化

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

优化动态规划的时间复杂度，主要有如下几种：

一，不同的状态表示。

比如：n个人，m顶帽子。

第一种方式：dp[i][mask] ,i表示前i个人已经选择帽子，mask 表示 那些帽子已经选择。 空间复杂度：O(n2m)。

第二种方式：dp[i][mask] ,i表示前i个帽子已经选择，mask表示那些人已经选择。 空间复杂度：O(m22)。

n大，则现在方式一；否则选择方式二。

【状态压缩】【动态规划】【C++算法】1125.最小的必要团队

二，通过优化状态减少状态数

例一

【动态规划】【C++算法】2518. 好分区的数目

num的长度 ∈ \in ∈[1,1000],num[i] ∈ \in ∈[0,106] k ∈ \in ∈[0,1000]。

将num的元素放到两个数组中，两个数组的和都为k。

由于num[i] >=0，所以 数组和已经大于k 的无论如何都不会等于k，抛弃。

dp[k1][k2] 的状态数是固定。

当处理完 n u m [ 0 , i ) 时 , 两个数组的和是固定    ⟺    k 1 + k 2 ≡ ∑ j : 0 i − 1 n u m s [ j ] 当处理完num[0,i)时,两个数组的和是固定 \iff k1+k2 \equiv \sum\Large_{j:0}^{i-1} nums[j] 当处理完num[0,i)时,两个数组的和是固定⟺k1+k2≡∑j:0i−1​nums[j]

我记录k1或k2就可以了。新问题是k1 可能是5e8。

{ k 1 k 1