資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢移除迴文子列表所需的運算次數
假設我們有一個稱為nums的數字列表。現在讓我們考慮一個操作，其中我們刪除一些作為迴文的子列表。我們必須找到使列表為空所需的最小操作次數。
因此，如果輸入類似於nums = [6, 2, 4, 4, 2, 10, 6]，則輸出將為2，因為我們可以先刪除子列表[2, 4, 4, 2]，然後列表變為[6, 10, 6]，這也是一個迴文，因此將其刪除以使列表為空。
為了解決這個問題，我們將遵循以下步驟：
定義一個大小為105 x 105的陣列dp。
定義一個函式dfs()，它將接收i、j和一個數組v作為引數。
ret := inf
如果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 := (ret, 1 + (dfs(i + 1, j, v)和dfs(i, j - 1, v)的最小值))的最小值
如果v[i]與v[j]相同，則：
ret := ret和dfs(i + 1, j - 1, v)的最小值
初始化k := i + 2，當k < j時，更新（增加k的值），執行：
如果v[i]與v[k]相同，則：
ret := ret和dfs((i + 1, k - 1, v) + dfs(k + 1, j, v))的最小值
返回dp[i, j] = ret
從主方法執行以下操作：
用-1填充dp
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
更新於： 2020年12月22日
202 次瀏覽
廣告