PHP 알고리즘 학습의 동적 프로그래밍 (2)

이전에 동적 프로그래밍의 개념과 해결 단계를 간략하게 소개했지만, 공부하면서 동적 프로그래밍의 적용 범위가 너무 유연하다고 느꼈습니다. 여기서는 몇 가지 일반적인 질문을 선택하여 더 연습해 보겠습니다.

1. 가장 긴 공통 부분 수열(문자열 관련)

두 개의 문자열이 주어지면 가장 긴 공통 부분 수열(LCS)을 찾아 LCS의 길이를 반환합니다. 예:
예: "ABCD" 및 "EDCA"가 주어지면 LCS는 "A"(또는 D 또는 C)이고,
"ABCD" 및 "EACB"가 주어지면 LCS는 "입니다. AC"는 2를 반환합니다.

아이디어: 길이가 m인 문자열 a와 길이가 n인 문자열 b, 이들의 가장 긴 공통 부분 수열 긴[m][n]은 길이가 m-1인 a와 n-1을 통과할 수 있습니다. 길이 b가 추론됩니다. : a[m]이 b[n]과 같을 때 가장 길다[m][n] = 가장 길다[m-1][n-1] + 1; a[m]이 b[n]과 같지 않을 때, 가장 길다[m][n]=최대(가장 길다[m-1][n], 가장 길다[m][n-1]). 문자열 a 또는 b가 빈 문자열인 경우 해당 문자열과 다른 문자열 사이의 가장 긴 공통 부분 수열은 0이어야 합니다. 마지막 질문에 대한 답은 가장 길다[strlen(a)][strlen(b)]입니다.
코드:

2. 거리 편집(문자열 관련)

두 단어 word1과 word2가 주어지면 word1을 다음과 같은 최소 연산 수로 계산합니다. 단어2.
문자 삽입, 문자 삭제, 문자 바꾸기 총 3가지 작업 방법이 있습니다.
예: work1="mart" 및 work2="karma"가 주어지면 3을 반환합니다.

아이디어: 길이가 m인 문자열 a와 길이가 n인 문자열 b(m과 n은 모두 0보다 큼)에 대해 a[m]이 b[n]과 같지 않으면 a는 다음과 같습니다. b 최소 연산 횟수 = min(a[m-1]이 b[n]+1이 되기 위한 최소 연산 횟수, a[m]이 b[n-1]+1이 되기 위한 최소 연산 횟수 , a[m-1 ]은 b[n-1]이 됩니다. a[m]이 b[n]과 같으면 a[m]은 b[n]이 됩니다. 1]은 b[n-1]에 대한 최소 연산 수가 됩니다.
코드:

3. 배낭 문제

n개 항목의 부피 A[i]와 값 V[i]를 고려하면, m 사이즈 배낭에 넣을 수 있는 최대 총 가치는 얼마입니까?
예: 아이템 볼륨이 [2, 3, 5, 7]이고 해당 값이 [1, 5, 2, 4]인 경우 배낭 크기가 10이라고 가정하면 적재할 수 있는 최대 값은 9입니다.

아이디어: 공간이 v일 때 임의의 항목 i에 대해 i를 넣을 수 있으면(v가 무게[i]보다 크거나 같음) v 공간의 값 f(v)는 이때 는 f(v -weight[i]) + 값[i]와 같으므로 모든 항목을 순회하면 공간이 v일 때 얻을 수 있는 최대값을 찾을 수 있습니다.
코드:

4. 간격 문제(구글 인터뷰 질문)

n개의 동전이 한 줄로 늘어서 있는데, 동전마다 모양이 다릅니다. 값. 두 참가자는 동전이 모두 남을 때까지 양쪽에서 번갈아 가며 동전을 가져옵니다. 획득한 코인의 총 가치를 계산하여 가장 높은 가치를 지닌 코인이 승리합니다. 첫 번째 플레이어가 패할지, 승리할지 결정해주세요.
예: 배열 [3,2,2]가 주어지면 true를 반환하고, 배열 [1,20,15]가 주어지면 false를 반환합니다.

아이디어: 주어진 닫힌 간격(i에서 j, j는 i보다 크거나 같음) 동안 플레이어 A는 왼쪽에서 또는 오른쪽에서 동전을 가져오는 두 가지 방법만 있습니다. 왼쪽부터 가져오면 A가 얻을 수 있는 최대 액면가 = 획득한 동전의 액면가 + 남은 간격의 총 액면가 - 플레이어 B가 남은 간격에서 얻을 수 있는 최대 액면가입니다. A가 오른쪽에서 취하는 상황과 A가 왼쪽에서 취하는 경우는 다릅니다. 유사하게 취합니다. 이것으로부터 우리는 상태 전이 방정식을 얻을 수 있습니다. 두 개의 루프를 통해 길이 n의 순서로 i에서 j까지의 모든 간격의 전체 액면가와 j=i일 때 첫 번째 플레이어가 얻은 최대값(즉, i의 액면가)을 얻을 수 있습니다. -번째 동전).
코드:

위는 동적 프로그래밍을 배우는 PHP 알고리즘 내용입니다(2). 더 많은 관련 내용은 PHP 중국어 홈페이지(www.kr)를 참고해주세요. .php.cn)!