1222. Password dropping (interval DP, bracket matching)

 

It can be seen that it is a bracket match / Template question of the longest palindrome subsequence

initialization ： All defined as 0

The border ： Because a single character is also a palindrome subsequence ,dp[i][i]=1

State calculation / subset division ： According to whether the characters at both ends are in the longest palindrome subsequence , It can be divided into the following four subsets without repetition and leakage

• s[i] and s[j] All in palindrome subsequence             dp[i][j]=max(dp[i+1][j-1]+2)
• s[i] In palindrome subsequence                         dp[i][j]=max(dp[i][j-1])
• s[j] In palindrome subsequence                         dp[i][j]=max(dp[i+1][j])
• s[i]s[j] Are not in the palindrome subsequence             dp[i][j]=max(dp[i-1][j-1])

According to the state representation ,si In palindrome subsequence , It can be considered as a collection dp[i][j-1] in

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1005;
int dp[N][N];
int main()
{
    string s;
    cin>>s;
    s=" "+s;
    int n=s.size();
    for(int i=1;i<=n;i++)
        dp[i][i]=1;
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            if(s[i]==s[j])
                dp[i][j]=dp[i+1][j-1]+2;
                
        }
    cout<<n-dp[1][n]-1;
    return 0;
}