Sətirin kəsilməsi#7447

Sətirin kəsilməsi (Həll təhlili)

Let $d p [l] [r] = f (l, r)$ dp[l][r] = f(l, r) be the minimum number of characters that need to be deleted from the substring $s_{l} ... s_{r}$ s_l ... s_r so that, by performing the allowed operations (removing two identical adjacent characters), we can obtain an empty string. Then:

$f (l, r) = 0$ f(l, r) = 0, if $l > r$ l > r;
$f (l, l) = 1$ f(l, l) = 1, since the single character must be deleted in advance;
$f (l, r) = f (l + 1, r - 1)$ f(l, r) = f(l + 1, r - 1), if $s [l] = s [r]$ s[l] = s[r]. In this case, the inner part of the substring is deleted first, after which the boundary characters become adjacent and can be removed;

$f (l, r) = 1 + f (l + 1, r)$ f(l, r) = 1 + f(l + 1, r), if the first character is deleted;
$f (l, r) = 1 + f (l, r - 1)$ f(l, r) = 1 + f(l, r - 1), if the last character is deleted;

However, both of these cases can be conveniently generalized as follows: to solve the problem on the segment $[l; r]$ [l; r], split it into two subsegments $[l; i]$ and $[i + 1; r] (l \leq i < r)$ [i + 1; r]~(l \le i < r) and choose the minimum value:

f (l, r) = l \leq i < r min (f (l, i) + f (i + 1, r))

f(l, r) = \min_{l \le i < r} (f(l, i) + f(i + 1, r))

For example:

deleting the first character is equivalent to choosing $i = l (f (l, l) = 1)$ i = l~(f(l, l) = 1);
deleting the last character is equivalent to choosing $i = r - 1 (f (r, r) = 1)$ i = r - 1~(f (r, r) = 1).

The answer to the problem will be $d p [0] [n - 1] = f (0, n - 1)$ dp[0][n - 1] = f(0, n - 1), where $n$ is the length of the input string.

Example

Let’s consider the example given in the problem statement. We have:

f (0, 7) = f (0, 2) + f (3, 7) = 1 + 1 = 2

f(0, 7) = f(0, 2) + f(3, 7) = 1 + 1 = 2

Algorithm implementation

Let's declare the constants and the array.

#define MAX 101
#define INF 0x3F3F3F3F
int dp[MAX][MAX];

The function f solves the problem on the segment $[l; r]$ [l; r].

int f(int l, int r) 
{

First, consider the base cases.

  if (l > r) return 0;
  if (l == r) return 1;

If the value $d p [l] [r]$ dp[l][r] is already computed, return it.

  if (dp[l][r] != INF) return dp[l][r];

If the characters $s [l]$ and $s [r]$ are equal, they do not need to be removed in advance. First, we clear the middle part of the segment; after that, these characters become adjacent and can be removed for free.

  int &res = dp[l][r];
  if (s[l] == s[r]) 
    res = min(res, f(l + 1, r - 1));

Consider splitting the segment $[l; r]$ [l; r] into two parts: $[l; i]$ and $[i + 1; r]$ [i + 1; r]. Solve the problem independently for each subsegment and take the minimum result.

  for (int i = l; i < r; i++)
    res = min(res, f(l, i) + f(i + 1, r));

Finally, return the computed value.

  return res;
}

The main part of the program. Read the input string.

cin >> s;
memset(dp,0x3F,sizeof(dp));

Compute and print the result $f (0, n - 1)$ f(0, n - 1), where $n$ is the length of the string $s$ .

printf("%d\n",f(0, s.size() - 1));

Java implementation

import java.util.*;

public class Main 
{
  static String s;
  static int dp[][];

  static int f(int l, int r)
  {
    if (l > r) return 0;
    if (l == r) return 1;
    if (dp[l][r] != Integer.MAX_VALUE) return dp[l][r];

    int res = dp[l][r];
    if (s.charAt(l) == s.charAt(r))
      res = Math.min(res, f(l + 1, r - 1));

    for (int i = l; i < r; i++)
      res = Math.min(res, f(l, i) + f(i + 1, r));
    return dp[l][r] = res;
  }
	
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    s = con.nextLine();
    int n = s.length();
    dp = new int[n][n];
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      dp[i][j] = Integer.MAX_VALUE;
 
    System.out.println(f(0, n - 1));
    con.close();
  }
}

Java

Python implementation

Declare the constant $I N F$ .

INF = float('inf')

The function f solves the problem on the segment $[l; r]$ [l; r].

def f(l, r):

First, consider the base cases.

  if l > r: return 0
  if l == r: return 1

If the value $d p [l] [r]$ dp[l][r] is already computed, return it.

  if dp[l][r] != INF:
    return dp[l][r]

  res = dp[l][r]
  if s[l] == s[r]:
    res = min(res, f(l + 1, r - 1))

Consider splitting the segment $[l; r]$ [l; r] into two parts: $[l; i]$ and $[i + 1; r]$ [i + 1; r]. Solve the problem independently for each subsegment and take the minimum result.

  for i in range(l, r):
    res = min(res, f(l, i) + f(i + 1, r))
  dp[l][r] = res
  return res

The main part of the program. Read the input string $s$ and compute its length $n$ .

s = input()
n = len(s)

Initialize the list $d p$ .

dp = [[INF] * n for _ in range(n)]

Compute and print the result $f (0, n - 1)$ f(0, n - 1).

print(f(0, n - 1))