lc718 동적 기획의 제목
4242 단어 동적 기획
두 개의 정수 그룹 A와 B를 주고 두 그룹의 공통적이고 길이가 가장 긴 하위 그룹의 길이를 되돌려줍니다.
여기에 동적 기획을 사용하는 것을 고려한다. 예를 들어 이런 출력 값을 사용하는 문제, 그리고 이런 교체된 느낌을 가진 문제는 동적 기획의 사고방식을 고려한다.
동태 계획의 사고방식은 상태 이동과 교체에 있다.
길이가 5와 길이가 4인 그룹의 최장자 그룹을 생각해 보세요. 상태가 바뀌려면 최소한 상태가 연속되어야 하기 때문에 dp의 상태는 이 인덱스를 오른쪽의 최장자 그룹으로 설정할 수 있습니다. dp[4][3]는 마지막 숫자로 오른쪽으로 구성된 최장자 그룹으로 표시할 수 있습니다.만약 A[4]!=B[3], 그럼 dp[4][3]는 0.만약에 A[4]=B[3]라면 dp[4][3]=dp[3][2]+1, 이것이 바로 전이 방정식이다.
다음은 어떻게 계획하고 초기치를 어떻게 정하는가이다.여기는 전이 방정식의 한 상태 인덱스가 모두 이전 줄에 있기 때문에 가로로 쓸면 됩니다.
여기서 주의해야 할 것은 2차원 dp수조는 절대로 이렇게 dp=[[0](len(A)+1)](len(B)+1)]을 만들 수 없다는 것이다. 이렇게 만들면 모든 하위 목록의 바늘은 주소이다.
코드는 다음과 같습니다.
dp = [[0 for x in range(len(A)+1)] for y in range(len(B)+1)]
res = 0
for i in range(1,len(B)+1):
for j in range(1,len(A)+1):
if B[i-1]==A[j-1]:
dp[i][j]=dp[i-1][j-1]+1
res = max(dp[i][j],res)
return res
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
