一道不错的DP题目！
首先看到每次可以取任意一个nums[l] ~ nums[r]的子集
- 不能用贪心（无法找到全局最优解）
- 不能用搜索 （数据规模太大，(2^10) ^ 1000）
那只能用动态规划了
状态定义: dp[k][i][j] 能否通过使用前k个变换使得第i个数的值变成j
边界条件: dp[0][i][nums[i]] = 1，不使用任何变换，第i个数可以达到的数值就是nums[i]本身。
状态转移：dp[k][i][j] = dp[k-1][i][j] | (dp[k – 1][i][j + val[k]] if l[k] <= i <= r[k] else 0)
简单来说如果第k-1轮第i个数可以变成j + val[k]，那么第k轮就可以通过减去val[k]变成j。
上面是拉的公式，我们也可以写成推的:
dp[k][i][j – val[k]] = dp[k-1][i][j – vak[k]] | (dp[k – 1][i][j] if l[k] <= i <= r[k] else 0)
当然这么定义的话空间复杂度太高O(10^7)，由于第k轮的初始状态就等于k-1轮的状态，我们可以使用滚动数组来降维，空间复杂度降低到O(10^4)。
时间复杂度：O(k*n*MaxV) = O(10^7)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public: int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) { if (accumulate(begin(nums), end(nums), 0) == 0) return 0; constexpr int kMaxV = 1000; const int n = nums.size(); const int K = queries.size(); vector<bitset<kMaxV + 1>> dp(n); for (int i = 0; i < n; ++i) dp[i][nums[i]] = 1; for (int k = 0; k < K; ++k) { int l = queries[k][0]; int r = queries[k][1]; int v = queries[k][2]; for (int i = l; i <= r; ++i) for (int j = 0; j <= kMaxV - v; ++j) if (dp[i][j + v]) dp[i][j] = 1; bool found = true; for (int i = 0; i < n; ++i) if (!dp[i][0]) found = false; if (found) return k + 1; } return -1; } }; |
剪枝优化
上面我们把整个数组看作一个整体，一轮一轮来做。但如果某些数在第k轮能到变成0了，就没有必要参与后面的变化了，或者说它用于无法变成0，那么就是无解，其他数也就不需要再计算了。
所以，我们可以对每个数单独进行dp。即对于第i个数，计算最少需要多少轮才能把它变成0。然后对所有的轮数取一个最大值。总的时间复杂度不变（最坏情况所有数都需要经过K轮）。空间复杂度则可以再降低一个纬度到O(MaxV) = O(10^3)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution { public: int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) { constexpr int kMaxV = 1000; const int n = nums.size(); const int K = queries.size(); auto rounds = [&](int i) -> int { if (!nums[i]) return 0; bitset<kMaxV + 1> dp; dp[nums[i]] = 1; for (int k = 0; k < K; ++k) { int l = queries[k][0]; int r = queries[k][1]; int v = queries[k][2]; if (l > i || r < i) continue; for (int j = 0; j <= kMaxV - v; ++j) if (dp[j + v]) dp[j] = 1; if (dp[0]) return k + 1; } return INT_MAX; }; int ans = 0; for (int i = 0; i < n && ans <= K; ++i) ans = max(ans, rounds(i)); return ans == INT_MAX ? -1 : ans; } }; |
再加速：我们可以使用C++ bitset的右移操作符，dp >> v，相当于把整个集合全部剪去v，再和原先的状态做或运算（集合并）来达到新的状态。时间复杂度应该是一样的，只是代码简单，速度也会快不少。注: dp>>v 会创建一个临时对象，大小为O(MaxV)。
举个例子：
dp = {2, 3, 7}
dp >> 2 -> {0, 1, 5}
dp |= dp >> v -> {0, 1, 2, 3, 5, 7]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public: int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) { constexpr int kMaxV = 1000; const int n = nums.size(); const int K = queries.size(); auto rounds = [&](int i) -> int { if (!nums[i]) return 0; bitset<kMaxV + 1> dp; dp[nums[i]] = 1; for (int k = 0; k < K; ++k) { int l = queries[k][0]; int r = queries[k][1]; int v = queries[k][2]; if (l > i || r < i) continue; dp |= dp >> v; // magic if (dp[0]) return k + 1; } return INT_MAX; }; int ans = 0; for (int i = 0; i < n && ans <= K; ++i) ans = max(ans, rounds(i)); return ans == INT_MAX ? -1 : ans; } }; |
