【LeetCode】3524. 求出数组的 X 值 I (动态规划)

3524. 求出数组的 X 值 I - 力扣（LeetCode）

题目：

思路：

简单题，学习到了处理子数组问题的一般思路

对于本题，如果我们暴力枚举显然是 O(N²) 的，所以考虑优化

注意到题目中的 k 很小，我们不妨考虑使用动态规划求解

在面对子数组问题时，我们通用思路是转变为 “计算 以 i 结尾的符合要求的子数组 的数量”，这样我们就能通过递推的方式来将时间复杂度优化掉

本题我们一样，我们定义 f[i][j] 是以 i 结尾，且余数为 j 的子数组的数量，那么考虑转移

①.不接上前面，由于我们可以只选自身，那么就有 f[i][nums[i] % k]++

②.接上前面，此时接上了前面我们该如何计算呢?

既然接上了前面，那么新的余数显然就是 x * nums[i] % k，然后转移即可

但是我们发现如果按照通常枚举 f[i][j] 的 j 是不好计算的，因为 j = x * nums[i] % k，对于枚举的 j 我们不好求出转移来的 x，所以我们这里将枚举 f[i-1][j] 的 j，即反向求出转移的目的地，那么代码就是 f[i][j * nums[i] % k] += f[i-1][j]

至此结束，注意点为下标处理，这里填充一个无用元素将下标后移，同时注意开long long，转移过程不能爆 int

代码：

class Solution {
public:vector<long long> resultArray(vector<int>& nums, int k) {int n = nums.size();nums.insert(nums.begin(), 0);vector<vector<long long>> f(n + 1, vector<long long>(k, 0));for (int i = 1; i <= n; i++) {f[i][nums[i] % k]++;for (int j = 0; j < k; j++) {f[i][(1LL*j*nums[i])%k] += f[i-1][j];}}vector<long long> ans(k, 0);for (int i = 1; i <= n; i++) {for (int j = 0; j < k; j++) {ans[j] += f[i][j];}}return ans;}
};