알고리즘 커닝 페 이 퍼

동적 계획
동적 계획 3 요소

중첩 자 문제: 중복 계산

최 우수 서브 구조: 서브 문 제 를 통 해 원래 문제 의 가장 가치 있 는 가치

상태 전이 방정식: 정확 한 '상태 전이 방정식' 을 열거 해 야 정확하게 들 수 있다

#    base case
dp[0][0][...] = base
#      
for   1 in   1     ：
      for   2 in   2     ：
          for ...
              dp[  1][  2][...] =    (  1，  2...)

1. 베이스 케이스 를 확인한다.2. '상태' 를 확인한다. 즉, 원래 문제 와 서브 문제 에서 변화 할 수 있 는 변수 이다.3. '선택' 을 확정 하 는 것 은 '상태' 에 변 화 를 일 으 키 는 행위, 즉 '선택' 이다.4. dp 함수 / 배열 의 정 의 를 명 확 히 합 니 다.
기본 동적 계획: 1 차원

509. 피 보 나치 수 (간단) 상태 전이 방정식: dp [i] = dp [i - 1] + dp [i - 2], 상태 압축 사용 가능

322. 잔돈 교환 (중간) 상태 이전 방정식: dp [i] = min (dp [i], 1 + dp [i - coin]);

70. 계단 오 르 기 (간단) 상태 이동 방정식: dp [i] = dp [i - 1] + dp [i - 2], 상태 압축 사용 가능

198. 약탈 (간단) 상태 전이 방정식: dp [i] = max (nums [i - 1] + dp [i - 2], dp [i - 1]), 상태 압축 사용 가능

413. 등차 수열 구분 (중간) 상태 전이 방정식: dp [i] = dp [i - 1] + 1, dp 표 구 와 최종 결 과 를 얻어 야 합 니 다

기본 동적 계획: 2 차원
입력 이 2 차원 일 때 2 차원 dp 배열 을 정의 합 니 다.

64. 최소 경로 와 (중간) 상태 전이 방정식:

   if(i==0&&j==0)
       dp[0][0] = grid[0][0];
   else if(i==0)
       dp[i][j] = dp[i][j-1] + grid[i][j];
   else if(j==0)
       dp[i][j] = dp[i-1][j] + grid[i][j];
   else
       dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];

542. 01 행렬 두 방향의 상태 전이 방정식:

     dp[i][j] = Math.min(dp[i][j],dp[i-1][j]+1);
     dp[i][j] = Math.min(dp[i][j],dp[i][j-1]+1);

     dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1);
     dp[i][j] = Math.min(dp[i][j],dp[i][j+1]+1);

221. 최대 정사각형 상태 전이 방정식: dp [i] [j] = Math. min (Math. min (dp [i - 1] [j], dp [i] [j - 1]), dp [i - 1] [j - 1]) + 1;maxEdge = Math.max(maxEdge,dp[i][j]);

하위 시퀀스 문제
300. 최 장 증자 시퀀스 base case: dp [i] = 1 상태 전이 방정식: for (int j = 0; j < i; j +) {if (nums [i] > nums [j]) {dp [i] = Math. max (dp [j] + 1, dp [i])} 354.먼저 너비 w 를 오름차 순 으로 정렬 하고 w 와 같은 상황 이 발생 하면 높이 h 내림차 순 으로 정렬 합 니 다.그 다음 에 모든 h 를 하나의 배열 로 하고 이 배열 에서 LIS 의 길 이 를 계산 하 는 것 이 답 이다.
1143. 최 장 공공 서브 시퀀스 dp 배열 정의: dp [i] [j] 의 미 는 s1 [0. i - 1] 과 s2 [0. j - 1], LCS 길 이 는 dp [i] [j] base case: dp [0] 와 dp [0] 를 0 으로 초기 화 하 는 것 으로 빈 문자열 상태 전이 방정식 을 나타 낸다. if (text1. charat (i - 1) = = (text2. charat (j - 1) dp [j] = dp [i - 1] [j - 1] + 1;else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
거리 문제 편집
72. 거리 상태 전이 방정식 편집: 똑 같이 변 하지 않 고 추가 삭제 if (word1. charAt (i - 1) = word2. charAt (j - 1) dp [i] [j] = dp [i - 1] [j - 1];else{ dp[i][j] = min(dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1); }
질문
53. 최대 하위 순서 와 dp 배열 의 정의: dp [i] 는 nums [i] 로 끝 나 는 최대 하위 배열 과.상태 이동 방정식: dp [i] = Math. max (dp [i], dp [i - 1] + nums [i]);base case：dp[0] = nums[0]; 516. 최 장 답장 서브 시퀀스 dp 정의 가 비교적 특수 합 니 다. 하위 문자열 s [i... j] 에서 가장 긴 답장 서브 시퀀스 의 길 이 는 dp [i] [j] 입 니 다.
1312. 문자열 을 리 턴 문자열 의 최소 삽입 횟수 인 리 턴 문자열 의 dp 정 의 는 기본적으로 같 습 니 다. dp [i] [j] 는 i - j 하위 문자열 의 해당 값 상태 전이 방정식 을 표시 합 니 다. if (s. charAt (i) = s. charAt (j) dp [i] [j] = dp [i + 1] [j - 1];else dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
10. 정규 표현 식 일치
가방 문제
0 - 1 가방 dp [i] [j] 는 앞의 i 개 아 이 템 을 표시 하고 가방 용량 이 j 일 때 담 을 수 있 는 최대 가치 base case: dp [0] [:] = dp [0] = 0 은 0 개 아 이 템 또는 0 용량 을 표시 하 며 최대 가 치 는 0 상태 이전 방정식: if (num [i - 1] > j) dp [i] [j] = dp [i - 1] [j] else dp [i] [j] = Math. max (dp [i - 1] [j], dp [i - 1] [j - nums [i - 1] + vals [i - 1]);
부분 집합 가방 416. 분할 등 과 부분 집합 은 먼저 sum 을 구 합 했 고 가방 문제 로 바 뀌 었 습 니 다. N 개 아 이 템, sum / 2 의 수용 중량, 모든 아 이 템 의 무 게 는 nums [i] 입 니 다. 포장 방법 이 있 습 니까? 가방 을 가득 채 울 수 있 습 니까? dp [i] [j] 는 용량 이 j 인 가방 에 대해 i 개 아 이 템 을 사용 하면 base case: dp [0] = true: 가득 채 울 공간 이 없습니다. dp [0] [0] [:]= false: 아 이 템 이 없 으 면 상태 이동 방정식 을 가득 채 울 수 없습니다. if (nums [i - 1] > j) dp [i] [j] = dp [i - 1] [j]; else dp [i] [j] = dp [i - 1] [j] | dp [i - 1] [j - nums [i - 1]];
완전 가방: 아 이 템 수량 무한 518. 잔돈 교환 II
분할 형식 문제

279. 완전 제곱 수

데이터 구조
이 진 트 리
124. 이 진 트 리 의 최대 경로 와 105. 이전 순서 와 중간 순서 가 서열 구조 이 진 트 리 를 옮 겨 다 녔 다.
두 갈래 검색 트 리 700. 두 갈래 검색 트 리 의 검색 701. 두 갈래 검색 트 리 의 삽입 동작 98. 두 갈래 검색 트 리 450 을 검증 합 니 다. 두 갈래 검색 트 리 의 노드 를 삭제 합 니 다.