Back to Leetcode

Readme

Dynamic_Programming/3685.Subsequence-Sum-After-Capping-Elements/Readme.md

latest1.4 KB
Original Source

3685.Subsequence-Sum-After-Capping-Elements

对于n个元素,问是否可以组合出和为k的方案,就是一个典型的有界背包问题,用o(n*k)的时间复杂度可解。大致算法是:

cpp
for (int i=0; i<nums.size(); i++) {
  for (int c=k; c>=1; c--) {
    dp[c] |= dp[c-nums[i];
  }
}

对于此题而言,对于每一个给定的x,我们要用nums里所有小于x的元素,以及剩余的元素当做x使用,问是否能组合出和为k的方案。我们暂时先不考虑第二种用法,即只用nums里小于x的元素。我们发现,随着x的增大,其实第一个for循环里可选的元素种类的上界也在单调增大,故总体这依然是一个o(n*k)可解的问题。

然后更深入地思考,我们将x从小到大遍历的时候,可以不断提升i,从而加入所有不超过x的新nums[i],就可以不断更新dp。同时我们还需要考虑等于x的元素:因为capping的缘故,这样的元素有n-i个。此时我们需要考虑这额外的n-i个元素能否对于组成k有帮助。显然我们可以用同样的背包思想:

cpp
for (int j=1; j<n-i; j++) {
  if (dp[k-x*j]) {
     return true;
     break;
  }
}

注意,这个过程中我们只是判断是否能组合成k,不会去更新dp。我们始终保持dp[c]表示“能否用所有小于x的元素组成c”。这样,即使x变大,dp的定义依然适用。