DP 질문

6062 단어

DP 질문


이른바 회문 문자열, Palindromic Substring, 정렬과 역순과 같은 문자열을 가리킨다. 예를 들어aba=>aba

질문


상세한 제목은 leetcode 5.Longest Palindromic Substring은 "babad"가 "bab"로 되돌아오는 문자열 중 가장 긴 메모 하위 문자열을 찾습니다.
이 고전적인 문제는 DP로 풀 수 있는데 상태 방정식은 다음과 같다.
status(i,j)=(i+1 > j-1 || status(i+1,j-1) )&& (s[i] == s[j])
여기서 status(i, j)는 s[i]를 나타냅니다.s[j]가 회문 문자열인지 여부는 분명히 status(i, j)는 회문 문자이고 status(i+1, j-1)만 회문 문자이며 s[i]=s[j]이다.
왜 i+1 > j-1의 판단을 추가해야 하는지 주의해라. j = i + 1할 때 문자열에는 두 글자만 있기 때문에 s[i]가 s[j]와 같은지 판단하면 된다.
상태 방정식을 쓰자마자 전체 문제가 쉽게 풀렸다.참조 코드는 다음과 같습니다.
string longestPalindrome(string s) {
        int len = (int)s.size();
        bool status[len][len];
        memset(status,false,sizeof(status));
        for(int i = 0;i=0;i--){
            for(int j = i+1;j j-1) || status[i+1][j-1]) && (s[i] == s[j]);
                if(status[i][j] && (j-i+1)>maxLen){
                    maxLen = j-i+1;
                    left = i;
                }
            }
        }
        return s.substr(left,maxLen);
    }

리턴 문자열 분할


자세한 제목은 leetcode 132 참조.Palindrome Partitioning II 는 분할된 하위 문자열이 모두 회문 문자열임을 보장하는 기초 위에서 최소한의 절단 횟수를 되돌려줍니다.
이 문제는 또 하나의 초급 버전이 있는데 모든 가능한 분할 방식을 되돌려주는 것이다. 원제는leetcode131을 참고한다.Palindrome Partitioning, 이 문제는 일반적인 DFS 귀속 사고방식으로 해결할 수 있고 구체적인 해결 방법은 제가 DFS 시리즈를 쓸 때 상세하게 소개할 것입니다.만약 이 문제의 해답 방향을 위의 이 문제에 완전히 적용한다면 틀림없이 시간 초과 오류가 발생할 것이다. 왜냐하면 어떠한 상태 저장도 하지 않았기 때문이다.
그래서 중간 상태를 저장할 방법을 생각해야 한다. 다음에 말하고자 하는 이런 해법은 leetcode에서 시간 순위가 높지 않지만 이해하기 쉽다고 생각한다.
우선 문자의 서브열이 회문인지 아닌지에 대한 반복적인 판단을 피하기 위해 이전 문제의 방법에 따라 2차원status수조로 이 정보를 저장할 수 있으며 구체적인 절차는 위의 문제와 마찬가지로 중복 소개하지 않는다.
그리고 1차원수 그룹 dp[i]를 사용하여 하위 문자열 s.substr(0,i)가 회문 하위 문자열 조합의 최소 절단 횟수를 나타낼 수 있다. 이렇게 k(kstatus[k][i]== true가 있다고 가정하면 이때dp[i]는 dp[i] = dp[k-1]+1로 쓸 수 있다. 그러면 모든 k가 i보다 작고 가장 작은 dp[i] 값을 찾으며 마지막 dp[len-1]는 다음과 같다. 구체적인 코드는 다음과 같다.
int status[1500][1500];//  s  ，       
int minCut(string s) {
        int len = (int)s.size();
        int dp[len];
        dp[0]= 0;

        memset(status,false,sizeof(status));
        for(int i = 0;i=0;i--){
            for(int j = i+1;j j-1 || status[i+1][j-1]) && (s[i] == s[j]);
            }
        }

        for(int i = 1;i

최장 회신 하위 시퀀스(Subsequence)


여기서 이 문제와 첫 번째 가장 긴 회문 서브 문자열의 차이점을 설명하고자 한다. 즉, longest palindrome Substring과 longest palindrome Subsequence, Substring은 서브 문자열을 대표하고 선택한 문자열은 연속적이어야 하며 Subsequence 서브 서열은 연속을 요구하지 않는다. 예를 들어 abcdef에서 Subsequence는'abdf'가 될 수 있고 Substring의 하표는 반드시 연속적이어야 한다.
자세한 제목은 leetcode 516.Longest Palindromic Subsequence는 주어진 문자열에서 가장 긴 회문 서열의 길이를 찾아냅니다. 예를 들어 'bbbab' 를 입력하고 4 ('bbb') 를 출력합니다.
모든 회문 서열을 열거할 수 없기 때문에, 가장 긴 회문 서열의 정보를 2차원 그룹으로 저장하는 것을 고려할 수 있습니다. 예를 들어status(i, j)는 s[i]를 대표합니다.s[j] 사이의 가장 긴 회문 서열의 길이로 상태 방정식을 쓸 수 있습니다.
status(i,j) = max(status(i,j-1),status(i+1,j))
status(i,j) = max(status(i,j),stauts(i+1,j-1)) s[i] == s[j]
마지막으로 status (0,len-1) 를 되돌려 주십시오.
참조 코드는 다음과 같습니다.
int longestPalindromeSubseq(string s) {
        int len = (int)s.size();
        int status[len][len];
        memset(status,0,sizeof(status));
        for(int i = 0;i=0;i--){
            for(int j = i+1;j

복잡한 계산 회문 서열 개수 문제


마찬가지로 그 문제와 마찬가지로 Subsequence 문제입니다.
자세한 제목은 leetcode 730을 참조하십시오.Count Different Palindromic Subsequences 는 주어진 문자열에 반복되지 않는 하위 서열의 개수를 초대합니다. 결과가 매우 크기 때문에 최종 결과는 10^9+7 모드로 갑니다."bccb"를 입력하면 6 을 되돌려줍니다.
분명히 폭력 해제는 시간 초과 오류가 발생할 것입니다. 그러면 어떻게 dp를 사용하여 상태를 저장해야 합니까? status (i, j) 를 사용하여 s (i) 를 표시해야 합니다.s(j) 사이의 회문 서열의 개수, 상태 이동 방정식은 다음과 같은 몇 가지 상황으로 나뉜다.
  • 당s(i)!=s(j)시,
    이때, status(i, j) = status(i+1, j)+status)i, j-1)-status(i+1, j-1)
  • s(i)==s(j)일 때,
    다음과 같은 경우도 있습니다.
    '당s(i+1)...s(j-1) 사이에 s(i)와 같은 원소가 없으면
    status(i,j)=status(i+1,j-1)*2+2
    그중 2는 s(i), s(j) 두 개로 구성된 회문 서열을 증가시켰다.
    '당s(i+1)...s(j-1) 사이에 s(i)와 같은 원소가 하나 있으면
    status(i,j)=status(i+1,j-1)*2+1
    그중 1은 s(i)s(j) 두 개로 구성된 회문 서열이 증가했고, 단독 s(i)는 이미 계산했기 때문에 더 이상 추가할 필요가 없다.
    '당s(i+1)...s(j-1) 중 s(i)와 같은 원소가 여러 개 있으면
    status(i,j)=status(i+1,j-1)*2-status(low+1,high-1)
    그 중에서low,high는 각각 왼쪽에서 첫 번째와 s(i)가 같은 원소를 대표하고,high는 오른쪽에서 첫 번째와 s(j)가 같은 원소를 대표한다.뺀 중간 부분은 중복 계산된 s(i)s(low+1)...s(high-1)s(j)와 s(low)s(low+1)...s(high-1)s(high)

    • 마지막으로 설명해야 할 것은 결과가 넘칠 가능성이 높기 때문에 위의 모든 작업에서 status(i, j)에 대해 모델링 작업을 해야 하며 마지막까지 기다려서는 안 된다는 것이다.또한 연산에서 감작업과 관련되기 때문에 마이너스 값을 얻어 결과가 정확하지 않을 가능성이 높기 때문에status(i, j)가 마이너스일 때 모형을 덧붙여 플러스로 만들어야 한다. 상세한 코드는 다음과 같다.
    int status[1000][1000];
int countPalindromicSubsequences(string S) {
        int len = (int)S.size();
        int mod = 1000000007;
        memset(status,0,sizeof(status));
        for(int i = 0;i=0;i--){
            for(int j = i+1;j high){
                        status[i][j] = (2*status[i+1][j-1]+2)%mod;
                    }
                    else if(low == high){
                        status[i][j] = (2*status[i+1][j-1]+1)%mod;
                    }
                    else{
                        status[i][j] = (2*status[i+1][j-1] - status[low+1][high-1])%mod;
                    }
                }
                status[i][j] = status[i][j]<0?(status[i][j]+mod)%mod:status[i][j];
            }
        }
        return status[0][len-1];
    }
    BIG-IP ve Device Trust 만들기(실패 편)
    [GCC/Terraform] 서브넷에 VM 인스턴스를 만들고Firewall 라이센스 IP에서만 SSH 연결

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage