本题的翻译是:由原始的数组nums可以搞出一个新数组count,其中count[i]表示第i件物品的个数。我们要满足一系列客户quantity,每个客户需要quantity[i]个一样的物品。问是否能够合理分配物品给客户,使得所有客户都得到满足。
我们注意到m<10,这样小的条件几乎就是暗示我们会有算法复杂度关于2^m,那么明显可以想到bitmask,利用m位的二进制数就可以表示穷举出所有客户满意的状态(数值为1的bit表示对应的客户得到了满足)。另外题目中there are at most 50 unique values in the array的意思就是,count数组的长度不超过50,即物品的个数不超过50. 由此我们联想到了状态压缩的动态规划:令dp[i][state]表示前i件物品是否可以满足state状态的客户需求。
如何设计状态转移方程来计算dp[i][state]呢?依然是动态规划的套路,从第i件物品入手。我们考虑第i件物品的数量能够满足state里面的哪些客户?显然这些客户必然是state里面的一个子集。所以dp[i][state]为true的两个条件是:
- 我们能找到state里面的一个子集subset,其对应的客户需求的物品总数都能被第i件物品所满足,
- 并且对应的前驱状态dp[i-1][state-subset]也为true,即前i-1件物品能满足state-subset所对应的客户(即除去第i件物品满足的subset客户)。 以上两个条件都满足的话,那么就说明前i件物品能满足state对应的所有客户需求。
特别需要注意的是,dp[i][state]为true其实还有另外一种方式:就是如果dp[i-1][state]已经为true的话,我们甚至可以跳过subset的搜索。
关于时间复杂度:对于state的遍历里面再嵌套subset的遍历,时间复杂度并不是 2^m * 2^m,而是3^m。你可以想象,对于每一个bit,在外、里两层的状态只可能是10,11,00,而不可能出现01。所以总的时间复杂度是o(N*m*3^m)