학습 노트

요 며칠 DP 문제를 몇 개 보았으니 이제 작은 총결산을 합시다.저는 개인적으로 dp를 처음 배울 때 이 세 가지 고전적인 DP 문제를 먼저 알아야 한다고 생각합니다.그럼 이 세 가지 간단하지만 확실한 경전의 dp를 간단하게 설명해 드리겠습니다.
1. 국부 최대 및:
대체적으로 제목의 뜻은 이렇다. 일련의 숫자 a[n]에서 연속적인 숫자를 찾아내 그들의 것과 가장 큰 숫자를 만든다.이거 제일 큰 거랑 max 주세요.
가령 현재 a[i]로 끝날 때의 최대치sum[i]가 나왔다고 가정한다.그러면sum[i+1]에 대해 두 가지 상태가 있는데 첫 번째는 이전의sum[i]<0시,sum[i+1]=a[i+1];두 번째는sum[i]>=0일 때sum[i+1]=sum[i]+a[i+1];
그래서 얻은 동적 이동 방정식은 다음과 같다.

if(sum[i]<0)
	sum[i+1]=a[i+1];
else
	sum[i+1]=sum[i]+a[i+1];

모든sum를 구한 후에 한 번만 훑어보면 가장 큰sum[i], 즉max를 구하는 것이 요구된다.물론 하나의 변수sum를 직접 사용하여 단계별로 판단하고 값을 부여할 수 있으며 max를 구할 수 있다.(어떤 문제에서는 약간의 변형이 있을 수 있다. 예를 들어 항저우전기에 문제가 있는데 어떤 문제인지 잊어버렸다. 그는 너에게 max를 구할 뿐만 아니라 이 문자열의 위치도 찾아내라고 요구했다. ps: 두 개의 표시를 달면 된다)
2. 가장 긴 공통 서열을 구한다.
대체적으로 두 문자열 중에서 이 두 문자열의 가장 긴 공통 서열의 길이를 구하는 것이다.(이 문자열은 반드시 연속된 것은 아니다)
두 문자열을 a[n], b[n]로 설정합니다.그리고 2차원 그룹 dp[alen][blen];alen,blen은 각각 a,b의 길이를 나타내고 dp[i][j]는 a[i-1]와 b[j-1]로 끝날 때의 가장 긴 공공 서열의 길이를 나타낸다.
그래서 동적 이동 방정식은 다음과 같다.

dp[i][j] =0        (i==0||j==0)
dp[i][j] =dp[i-1][j-1]+1        (a[i-1]==b[j-1])
dp[i][j] =max ( dp[i][j-1] , dp[i-1][j] )        (a[i-1]!=b[j-1])

마지막으로 dp[alen][blen]이 구한 결과입니다.
3. 최장 증자 서열 구하기(LIS)
대체적으로 문제는 일련의 숫자 a[n]에서 연속적으로 가장 길게 증가하는 서열을 찾아내 그 길이를 구하는 것이다.
위의 두 문제를 통해 너는 사실 이 문제의 동적 이동 방정식도 매우 쉽게 찾을 수 있다는 것을 발견할 수 있을 것이다.dp[i]를 a[i-1]로 끝나는 숫자열에서 가장 긴 증가 서열의 길이로 설정합니다.그렇게 쉽게

dp[i] =max ( dp[j] )+1       dp[j] ={ dp[j] | j<i && a[j] < a[i] }；

가장 큰 dp[i]를 두루 찾아보는 것이 요구이다.
같은 이치: 가장 긴 체감 서열의 동적 이동 방정식은 다음과 같다.

dp[i] =max ( dp[j] )+1       dp[j] ={ dp[j] | j <i && a[j] > a[i] };

만약 이 세 방정식의 유도에 대해 구체적으로 자세히 알고 싶다면, 이 블로그를 보시기 바랍니다.http://hi.baidu.com/qingmuxiaoyao/item/9ee3f8cd2dacb37789ad9e59
DP에서 가장 중요한 것은 상태와 상태 사이의 이동이다. 상태 이동 방정식을 찾아 귀속 또는 점차적인 방식으로 방정식을 열거하면 제목도 바로 풀린다. 이른바 어려운 문제는 처음에 보면 어찌할 바를 모르고 상태 이동 방정식을 찾지 못하거나 상태가 무엇인지도 똑똑히 볼 수 없다.DP는 ACM의 알고리즘에서 가장 중요한 부분이라고 할 수 있다. 제목의 유형이 변화무쌍하고 제목의 난이도도 차이가 크다. 기교를 중시하는 알고리즘이고 코드의 실현이 상대적으로 쉬우며 1y율이 매우 높다(일부 bt 데이터 제외).한마디로 DP는 항상 매우 중요하고 심오한 알고리즘이다.