Posts published in “Dynamic Programming”

花花酱 LeetCode 646. Maximum Length of Pair Chain

By zxi on April 9, 2025

这题我选DP，因为不需要证明，直接干就行了。

方法1: DP

首先还是需要对pairs的right进行排序。一方面是为了方便chaining，另一方面是可以去重。

然后定义 dp[i] := 以pairs[i]作为结尾，最长的序列的长度。

状态转移：dp[i] = max(dp[j] + 1) where pairs[i].left > pairs[j].right and 0 < j < i.

解释：对于pairs[i]，找一个最优的pairs[j]，满足pairs[i].left > pairs[j].right，这样我就可以把pairs[i]追加到以pairs[j]结尾的最长序列后面了，长度+1。

边检条件：dp[0:n] = 1，每个pair以自己作为序列的最后元素，长度为1。

时间复杂度：O(n²)
空间复杂度：O(n)

class Solution {

public:

int findLongestChain(vector<vector<int>>& pairs) {

sort(begin(pairs), end(pairs), [](const auto& p1, const auto& p2){

return p1[1] < p2[1];

});

const int n = pairs.size();

vector<int> dp(n, 1);

for (int i = 0; i < n; ++i)

for (int j = 0; j < i; ++j)

if (pairs[i][0] > pairs[j][1])

dp[i] = max(dp[i], dp[j] + 1);

return *max_element(begin(dp), end(dp));

}

};

方法2: 贪心

和DP一样，对数据进行排序。

每当我看到 cur.left > prev.right，那么就直接把cur接在prev后面。我们需要证明这么做是最优的，而不是跳过它选后面的元素。

Case 0: cur已经是最后一个元素了，跳过就不是最优解了。

假设cur后面有next, 因为已经排序过了，我们可以得知 next.right >= cur.right。

Case 1: next.right == cur.right。这时候选cur和选next对后面的决策来说是一样的，但由于Case 0的存在，我必须选cur。

Case 2: next.right > cur.right。不管left的情况怎么样，由于right更小，这时候选择cur一定是优于next。

综上所述，看到有元素可以连接起来就贪心的选它就对了。

时间复杂度：O(nlogn)
空间复杂度：O(1)

class Solution {

public:

int findLongestChain(vector<vector<int>>& pairs) {

sort(begin(pairs), end(pairs), [](const auto& p1, const auto& p2){

return p1[1] < p2[1];

});

int right = INT_MIN;

int ans = 0;

for (const auto& p : pairs)

if (p[0] > right) {

right = p[1];

++ans;

}

return ans;

}

};

花花酱 LeetCode 514. Freedom Trail

By zxi on April 6, 2025

一眼DP，看数据规模标程应该是O(100³)。

阶段肯定就是吟唱完一个字符，状态和哪个字符在12:00点有关。

所以我们定义 dp[i][j] := 吟唱完keys[0~i]后，rings[j]停在12:00点所需要的最少步数。

转移方程：dp[i][j] = min(dp[i-1][k] + steps(k, j) + 1) if keys[i] == rings[j] else +inf.

第i-1字符吟唱完ring停留在k，第i个字符吟唱完ring停留在j (rings[j] 必须和 keys[i] 相同)，steps(k, j)表示ring从k转到j所需要的最少步数，最后还要+1，表示吟唱当前字符所需要的额外步骤。

边界条件：对于第0个字符，ring一开始停留在第0个字符，最小步数就是1 + steps(0, key[0])。

时间复杂度：O(mn²)
空间复杂度：O(mn) 可以降维到 O(n)

class Solution {

public:

int findRotateSteps(string ring, string key) {

const int n = ring.size();

const int m = key.size();

auto steps = [n](int i, int j) {

return min(abs(i - j), n - abs(i - j));

};

// dp[i][j] min steps to spell key[0~i] and ring[j] is at 12:00.

vector<vector<int>> dp(m, vector<int>(n, INT_MAX/2));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

if (ring[j] != key[i]) continue;

for (int k = 0; k < n; ++k)

dp[i][j] = min(dp[i][j], 1 + (i == 0 ? steps(0, j) : (dp[i - 1][k] + steps(j, k))));

}

return *min_element(begin(dp.back()), end(dp.back()));

}

};

花花酱 LeetCode 403. Frog Jump

By zxi on April 5, 2025

肯定是用DP，但我自己想了一个奇怪的方法，勉强过了…

使用dp[i] = {steps}，表示可以达到stones[i]的最后一跳的unit的集合。
dp[0] = {0}
dp[1] = {1} if stones[1] = 1 else {}
然后对于stones[i]，枚举所有step – 1, step, step + 1三种情况，看看是否可以跳到新的石头上面（使用一个hashtable判断），如果可以的吧，把跳的unit存到dp[j]中。相当于推了。
需要使用hashset去重，不然会超时。

时间复杂度：O(n²)
空间复杂度：O(n²)

class Solution {

public:

bool canCross(vector<int>& stones) {

if (stones[1] != 1) return false;

unordered_map<int, int> m;

const int n = stones.size();

for (int i = 0; i < n; ++i)

m[stones[i]] = i;

// dp[i] = {steps} steps to jump to stone[i].

vector<unordered_set<int>> dp(n);

dp[0] = {0};

dp[1] = {1};

for (int i = 2; i < n; ++i) {

for (int last : dp[i - 1]) {

for (int cur = last - 1; cur <= last + 1; cur++) {

if (cur < 1) continue;

const int t = stones[i - 1] + cur;

auto it = m.find(t);

if (it != end(m)) dp[it->second].insert(cur);

}

return !dp.back().empty();

}

};

“优化”：由于每次只能k-1,k,k+1steps，所以最大的units和n是线性关系，达到stones[i]最多跳i+1个units。
可以用二维数组dp[j][k] := 是否可以通过k步跳到stones[j].
dp[j][k] = dp[i][k-1] || dp[i][k] || dp[i][k+1], k = stones[j] – stones[i]. 即从stones[i]跳到stones[j]，并且要求跳到stones[i]的可能步数中存在k-1,k,k+1。
时间复杂度和空间复杂度是一样的。

class Solution {

public:

bool canCross(vector<int>& stones) {

const int n = stones.size();

vector<vector<bool>> dp(n, vector<bool>(n + 1));

dp[0][0] = true;

for (int i = 1; i < n; ++i)

for (int j = 0; j < i; ++j) {

const int d = stones[i] - stones[j];

if (d >= n) continue; // undefined range.

dp[i][d] = dp[i][d] || (dp[j][d - 1] || dp[j][d] || dp[j][d + 1]);

}

return any_of(begin(dp.back()), end(dp.back()), [](bool x) { return x; });

}

};

花花酱 LeetCode 368. Largest Divisible Subset

By zxi on April 4, 2025

也算是一道比较经典的DP题了，需要找到一个最大的子集，使得其中元素两两的余数为0。

我们假设有一个集合为{a1, a2, a3, …, an}, {a1 < a2 < … < an)

如果 a2 % a1 = 0, a3 % a2 == 0, 那么a3 % a1 一定也等于0。也就是说a2是a1的倍数，a3是a2的倍数，那么a3一定也是a1的倍数。所以我们并不需要测试任意两个元素之间的余数为0，我们只需要检测a[i]是否为a[i-1]的倍数即可，如果成立，则可以确保a[i]也是a[i-2], a[i-3], … a[1]的倍数。这样就可以大大降低问题的复杂度。

接下来就需要dp就发挥威力了。我们将原数组排序，用dp[i]来表示以a[i]结尾（集合中的最大值），能够构建的子集的最大长度。

转移方程：dp[j] = max(dp[j], dp[i] + 1) if nums[j] % nums[i] = 0.

这表示，如果nums[j] 是 nums[i]的倍数，那么我们可以把nums[j]加入以nums[i]结尾的最大子集中，构建一个新的最大子集，长度+1。当然对于j，可能有好多个满足条件的i，我们需要找一个最大的。

举个例子：
nums = {2, 3, 4, 12}
以3结尾的最大子集{3}，长度为1。由于12%3==0，那么我们可以把12追加到{3} 中，构成{3,12}。
以4结尾的最大子集是{2,4}，长度为2。由于12%4==0，那么我们可以把12追加到{2,4} 中，构成{2,4,12} 。得到最优解。

这样我们只需要双重循环，枚举i，再枚举j (0 <= i < j)。时间复杂度：O(n^2)。空间复杂度：O(n)。

最后需要输出一个最大子集，如果不记录递推过程，则需要稍微判断一下。

class Solution {

public:

vector<int> largestDivisibleSubset(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

// dp[i] = max size of subset ends with nums[i]

vector<int> dp(n);

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

if (nums[j] % nums[i] == 0)

dp[j] = max(dp[j], dp[i] + 1);

int s = *max_element(begin(dp), end(dp));

vector<int> ans;

for (int i = n - 1; i >= 0; --i) {

if (dp[i] == s && (ans.empty() || ans.back() % nums[i] == 0)) {

ans.push_back(nums[i]);

--s;

}

return ans;

}

};

花花酱 LeetCode 3489. Zero Array Transformation IV

By zxi on March 16, 2025

一道不错的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)。

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)。

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]

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;

}

};