hiho一下第233周《数组分拆》题目分析

1
0

《数组分拆》题目分析

这道题是一道DP题。首先我们比较容易能想到一个O(N^2)的DP。

我们用f[i]表示将A1 ~ Ai拆分成若干段使得每段和都不为0的方案数。考虑拆出的最后一段是A[j+1] ... Ai,有转移方程:

f[0] = 1

f[i] = Σf[j] | j = 0 .. i-1 且 A[j+1] .. Ai的和不为0。 

其中“A[j+1] .. Ai的和不为0”可以利用前缀和做到O(1)的判断。所以上述的DP是O(N)状态和O(N)的转移,总复杂度是O(N^2)的。

下面我们介绍如何将转移优化为O(1)的。如果我们令前缀和s[i] = f[0] + f[1] + ... f[i],那么显然上述转移方程直观上是:

f[i] 等于 f[0] .. f[i-1] 中若干项的和。具体是哪些项呢? 是那些满足s[j] != s[i]的f[j]。

于是我们可以换一种方法计算f[i]:先加上f[0] .. f[i-1],再减去那些满足s[j] == s[i]的f[j]:

f[i] = (Σf[j] | j = 0 .. i-1) - (Σf[j] | j = 0 .. i-1 且 s[i] == s[j])  

其中f[0] + f[1] + f[2] + .. + f[i-1]就是s[i-1]可以直接O(1)得到。

而第二部分“满足s[j] == s[i]的f[j]之和”我们可以用一个哈希表( unordered_map) h来记录,h[x]表示满足前缀和s[j]==x的f[j]之和。

h随着新的f[i]计算出来会更新,更新和查找的复杂度都是O(1)的。

于是我们就得到了转移O(1)的DP,总复杂度是O(N)的。

2 answer(s)

1

首先F[0]=1吧

f[i] = (Σf[j] | j = 0 .. i-1) - (Σf[j] | j = 0 .. i-1 且 s[i] == s[j])  中的s[i]并不是s[i] = f[0] + f[1] + ... f[i],而是单纯的A数组的前缀和吧
2

开始很容易直接想到一个O(n^2) 的动态规划。 令dp[i]表示i个数不同种划分数,sum[j,i]表示数组下标从j到i的和。 从划分思想,比较容易想到:

dp[i]=∑dp[j] (j<i&&sum[j,i]!=0)

其中sum[j,i]可以由前缀数组O(1)的得到。

但明显这题N<1e5,复杂度不够。 继续优化。 对于dp[i]求和这一步我们同样用前缀数组优化。 定义: dp_sum[i] = ∑ dp[i]

那么对于dp[i] = dp_sum[i-1] - 数量(∑ sum[j+1,i]=0)

对于sum[j+1,i]=0,我们两边同时加上sum[0,j],就变成:sum[0,i] = sum[0,j]。问题变成减去出现sum[0,i] = sum[0,j]的数量,也就是减去前缀和为sum[0,i]的数量。 ``于是我们只需要一个Hash表去保存前缀和sum[0,i]出现的个数。时间复杂度O(1)求出sum[0,i]的数量。

则转移方程:dp[i] = dp_sum[i-1] - Hash[sum[0,i]]

  • dp[i] = dp_sum[i-1] - 数量(∑ sum[j+1,i]=0) 这个公式怎么理解呀, 不应该减去∑ sum[j+1,i]=0对应的d[j]吗 这里的数量是啥意思

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享