समस्या विवरण
मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। अब एक ऑपरेशन पर विचार करें जहां हम कुछ सबलिस्ट को हटाते हैं जो एक पालिंड्रोम है। हमें न्यूनतम ऑपरेशन्स की संख्या ढूंढनी है ताकि सूची खाली हो जाए।
उदाहरण के लिए, यदि इनपुट है nums = [6, 2, 4, 4, 2, 10, 6], तो आउटपुट 2 होगा, क्योंकि हम पहले सबलिस्ट [2, 4, 4, 2] को हटा सकते हैं फिर सूची [6, 10, 6] जैसी हो जाती है यह भी एक पालिंड्रोम है, इसलिए इसे हटाकर सूची खाली करें।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- आकार 105×105 का एक DP ऐरे परिभाषित करें
- एक फंक्शन dfs() परिभाषित करें जो i, j, और ऐरे v लेता है
- ret := अनंत
- यदि i > j, तो 0 वापस करें
- यदि i == j, तो 1 वापस करें
- यदि j - i == 1, तो (यदि v[i] == v[j] तो 1 अन्यथा 2) वापस करें
- यदि i+1 ≤ j और v[i] == v[i+1], तो ret := 1 + dfs(i+2, j, v)
- यदि dp[i][j] != -1, तो dp[i][j] वापस करें
- ret := min(ret, 1 + min(dfs(i+1, j, v), dfs(i, j-1, v)))
- यदि v[i] == v[j], तो ret := min(ret, dfs(i+1, j-1, v))
- k := i+2 से j-1 तक:
- यदि v[i] == v[k], तो ret := min(ret, dfs(i+1, k-1, v) + dfs(k+1, j, v))
- dp[i][j] = ret वापस करें
- मुख्य विधि से:
- dp को -1 से भरें
- n := nums का आकार
- dfs(0, n-1, nums) वापस करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int dfs(int i, int j, vector<int>& v) {
int ret = INT_MAX;
if (i > j) return 0;
if (i == j) return 1;
if (j - i == 1) {
return v[i] == v[j] ? 1 : 2;
}
if (i + 1 <= j && v[i] == v[i + 1]) {
ret = 1 + dfs(i + 2, j, v);
}
if (dp[i][j] != -1) return dp[i][j];
ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
if (v[i] == v[j]) {
ret = min(ret, dfs(i + 1, j - 1, v));
}
for (int k = i + 2; k < j; k++) {
if (v[i] == v[k]) {
ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
}
}
return dp[i][j] = ret;
}
int solve(vector<int>& nums) {
memset(dp, -1, sizeof dp);
int n = nums.size();
return dfs(0, n - 1, nums);
}
int main() {
vector<int> v = {6, 2, 4, 4, 2, 10, 6};
cout << solve(v);
}
इनपुट
{6, 2, 4, 4, 2, 10, 6}
आउटपुट
2
