Solve the problem of adding the least number of parentheses (interval DP)

The question ：

The sequence of parentheses consists of (),[],{}, form , for example (([{}]))() It's legal. , and (}{) and （}（} It's all illegal . If a sequence is illegal , Write a program , Add the minimum number of parentheses , Make this sequence legal . for example (}(} Add at least 4 Brackets become legal , Become (){}(){}.

Ideas ： Classical interval dp problem , Definition f[l][r] For will c[l] to c[r] The minimum number of parentheses that become legal .

Then when c[l] == c[r] when ,f[l][r] = f[l + 1][r - 1]

When c[l] != c[r] when , f[l][r] = min(f[l + 1][r], f[l][r - 1]) + 1;

Consider again l~r Decision making divided into two intervals f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r])

See code for details ：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

char c[N];
int n, f[N][N];

bool cheak(char a, char b)
{
	if(a == '[' && b == ']') return true;
	if(a == '(' && b == ')') return true;
	if(a == '{' && b == '}') return true;
	return false;
}

int main()
{
	scanf("%s", c);
	n = strlen(c);
	
	for(int len = 1; len <= n; len ++ )
	for(int l = 0; l + len - 1 < n; l ++ )
	{
		int r = l + len - 1;
		if(len == 1) f[l][r] = 1;	            // initialization 								
	
		else
		{
			f[l][r] = 0x3f3f3f3f;
			if(cheak(c[l], c[r])) f[l][r] = f[l + 1][r - 1];
		//	else f[l][r] = min(f[l + 1][r] + 1, f[l][r - 1] + 1);    This decision is contained in the following circular enumeration , So you can comment out 
			
			for(int k = l; k < r; k ++ )
			f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
		}
	}
	
	cout << f[0][n - 1] << endl;
	return 0;
}