資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++迴文刪除
假設我們有一個名為arr的整數陣列，現在我們可以一步操作從索引i到j（其中i <= j）選擇一個迴文子陣列，並將該子陣列從給定陣列中刪除。需要注意的是，刪除子陣列後，該子陣列左側和右側的元素會移動到刪除處填補空缺。我們需要找到刪除陣列中所有數字所需的最小移動次數。
例如，如果輸入為arr = [1,3,4,1,5]，則輸出為3，因為我們可以按此順序刪除：[4]，然後刪除[1,3,1]，最後刪除[5]。
為了解決這個問題，我們將遵循以下步驟：
n := arr的大小
定義一個大小為(n + 1) x (n + 1)的二維陣列dp
初始化l := 1，當l <= n時，更新（l加1），執行：
初始化i := 0，j := l - 1，當j < n時，更新（i加1），（j加1），執行：
如果l等於1，則：
dp[i, j] := 1
否則
dp[i, j] := 1 + dp[i + 1, j]
如果i + 1 < n且arr[i]等於arr[i + 1]，則：
dp[i, j] := dp[i, j]和1 + dp[i + 2, j]中的最小值
初始化k := i + 2，當k <= j時，更新（k加1），執行：
如果arr[i]等於arr[k]，則：
dp[i, j] := dp[i, j]，dp[i + 1, k - 1] + dp[k + 1, j]中的最小值
返回dp[0, n - 1]
讓我們來看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimumMoves(vector<int>& arr) {
int n = arr.size();
vector<vector<int> > dp(n + 1, vector<int>(n + 1));
for (int l = 1; l <= n; l++) {
for (int i = 0, j = l - 1; j < n; i++, j++) {
if (l == 1) {
dp[i][j] = 1;
} else {
dp[i][j] = 1 + dp[i + 1][j];
if (i + 1 < n && arr[i] == arr[i + 1])
dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]);
for (int k = i + 2; k <= j; k++) {
if (arr[i] == arr[k]) {
dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);
}
}
}
}
}
return dp[0][n - 1];
}
};
main(){
Solution ob;
vector<int> v = {1,2};
cout << (ob.minimumMoves(v));
}輸入
[1,2]
輸出
2
更新於：2020年7月11日
257 次瀏覽
廣告