数据结构
网络
关系数据库管理系统 (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 次浏览
广告