信息
- ID
- 802
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 57
- 已通过
- 23
- 上传者
dfs
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
string s;
int dp[105][105];
bool check(char a,char b)
{
if(a=='('&&b==')'||a=='['&&b==']')
return true;
return false;
}
int dfs(int l,int r)
{
if(l>r)
return 0;
if(dp[l][r])
return dp[l][r];
if(l==r)
return dp[l][r]=1;
dp[l][r]=100;
for(int i=l;i<r;i++)
dp[l][r]=min(dp[l][r],dfs(l,i)+dfs(i+1,r));
if(check(s[l],s[r]))
dp[l][r]=min(dp[l][r],dfs(l+1,r-1));
return dp[l][r];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>s;
s=" "+s;
cout<<dfs(1,s.size()-1)<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
// dp[i][j] s[i]~s[j] 这个子串最少加几个字符变成合法的
// 所有长度为0的区间,初始需要的步数都是0
int dp[105][105];
bool check(char a, char b)
{
return (a == '(' && b == ')') ||
(a == '[' && b == ']');
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
n = s.length();
s = " " + s; // 现在的每个字符是 s[1]~s[n]
for (int len = 1; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
// 计算 dp[l][r];
if (len == 1)
{
dp[l][r] = 1;
continue;
}
dp[l][r] = 100;
for (int k = l; k <= r - 1; k++)
{
// s[l]~s[k], s[k+1]~s[r]
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
}
if (check(s[l], s[r]))
dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
}
}
cout<<dp[1][n];
return 0;
}