동적 계획 - 최대 연속 하위 시퀀스 및

10614 단어 데이터 구조와 알고리즘
동적 계획 - 최대 연속 하위 시퀀스 및
  • 문제 설명은 숫자 서열 A1, A2,..., An, i, j(1<=i<=j<=n)를 지정하여 Ai+...Aj가 가장 크고 출력이 가장 크다.
  • 예 
    -2 11 -4 13 -5 -2
   11 + (-4) + 13 = 20          ，      20
    • 다음은 동적 기획의 방법을 소개한다. 복잡도는 O(n)이고 독자들은 사실 왼쪽 단점의 매거가 필요없다는 것을 발견할 수 있다.
  • 단계1: 상태 dp[i]로 하여금 A[i]를 끝으로 하는 연속 서열의 최대 합을 나타낸다(여기서 A[i]는 반드시 연속 서열의 끝으로 해야 한다).예를 들어 서열-211-413-5-2, 아래 표지는 각각 0,1,2,3,4,5로 기록된다. 그러면 
    dp[0] = -2,
dp[1] = 11,
dp[2] = 7 (11 + (-4)),
dp[3] = 20 (11 + (-4) + 13)
dp[4] = 15
dp[5] = 13 (11 + (-4) + 13 + (-5) + (-2))
    은 이런 dp수조를 설정함으로써 요구하는 최대와 사실은 dp[0], dp[1],..., dp[n-1]의 최대치(도대체 어떤 원소로 끝날지 알 수 없기 때문에) 다음에 방법을 강구하여 dp수조를 구한다.
  • 단계2: 다음과 같이 고려한다. dp[i]는 반드시 A[i]로 끝내야 하는 연속 서열이기 때문에 두 가지 상황만 있다.
  • 이 최대 화의 연속 서열은 단지 하나의 원소, 즉 A[i]로 시작하고 A[i]로 끝난다.
  • 이 가장 큰 합계의 연속 서열에는 여러 개의 원소가 있는데 그것이 바로 앞에 있는 A[p]에서 시작하여 A[i]까지 끝난다.첫 번째 상황에 대해 가장 큰 합은 바로 A[i] 자체이다.두 번째 상황에 대해 가장 큰 것은 dp[i-1]+A[i]이다. 이 두 가지 상황만 있기 때문에 상태 이동 방정식을 얻는다. dp[i]=max{A[i], dp[i-1]+A[i]}
  • 코드는 다음과 같습니다. 
    #include 
#include 
#include 

using namespace std;
const int maxn = 10010;
int A[maxn],dp[maxn];	// A[i]    ，dp[i]   A[i]           
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++){
        scanf("%d",&A[i]);
    }
    //   
    dp[0] = A[0];
    for(int i = 1 ; i < n ; i++){
        //       
        dp[i] = max(A[i],dp[i-1]+A[i]);
    }
    int k = 0;
    for(int i = 1 ; i < n ; i++){
        if(dp[i] > dp[k]){
            k = i;
        }
    }
    printf("%d
    "    ,dp[k]);
    return 0;
}
    • 4. 상태의 무후효성
    상태의 무후효성이란 현재 상태가 역사 정보를 기록하고 현재 상태가 확정되면 다시 바뀌지 않으며 미래의 결정은 기존의 한 개 또는 몇 개의 상태를 바탕으로 할 수 있고 역사 정보는 기존의 상태를 통해 미래의 결정에 영향을 미칠 수 있다.
    동적 기획이 풀 수 있는 문제에 대해 말하자면 많은 디자인 상태의 방식이 있지만 모든 상태가 후효성이 없는 것은 아니다. 따라서 반드시 후효성이 없는 상태와 상응하는 상태 이동 방정식을 설계해야 한다. 그렇지 않으면 동적 기획은 정확한 결과를 얻을 수 없다.사실상 상태와 상태 이동 방정식을 어떻게 설계하는가가 동적 기획의 핵심이고 동적 기획이 가장 어려운 부분이다.
    데이터 구조 - 기본 정렬 집합
    자동차 판매 관리 시스템 소스 코드

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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