LeetCode 문제 풀이 - 기초 지식 편 - 동적 기획

에서 동태 계획 에 관 한 지식 과 자신의 생각 을 기록 해 보 세 요.
동적 계획
동적 계획 은 조합 서브 문 제 를 통 해 원 문 제 를 해결 하 는 알고리즘 이다.동적 계획 은 하위 문제 가 중첩 되 는 상황 에 응용 된다. 즉, 서로 다른 하위 문 제 는 공공 적 인 하위 문 제 를 가진다 (하위 문제 의 구 해 는 재 귀적 으로 진행 되 고 이 를 더욱 작은 하위 문제 로 나 누 는 것).이런 상황 에서 동적 계획 알고리즘 은 모든 하위 문 제 를 한 번 만 풀 고 이 를 한 표 에 저장 하여 하위 문 제 를 풀 때마다 다시 계산 하지 않 아 도 불필요 한 계산 작업 을 피 할 수 있다.동적 계획 은 일반적으로 가장 최 적 화 된 문 제 를 해결 하 는 데 쓰 인 다.
동적 계획 알고리즘 을 설계 하면 보통 네 단계 로 나 눌 수 있다.

최 적 화 된 특징 치 를 묘사

재 귀 정의 최 적 화 된 값

가장 좋 은 값 을 계산 하고 보통 아래 에서 위로 올 라 가 는 방법

을 사용한다.

계 산 된 정 보 를 이용 하여 최 적 화 된 구 조 를 구축한다

절차 1 ~ 3 은 동적 계획 알고리즘 이 문 제 를 해결 하 는 기초 이다.만약 에 우리 가 그 자체 가 아 닌 가장 좋 은 값 만 필요 하 다 면 절 차 를 무시 할 수 있 습 니 다. 4. 절차 가 필요 하 다 면 3 절 차 를 실행 하 는 과정 에서 추가 정 보 를 유지 하여 최 적 화 를 구축 해 야 합 니 다.
동적 계획 원리
앞에서 언급 한 동적 계획 은 보통 '최적화 문제' 를 해결 하 는 데 쓰 인 다. 그러면 구체 적 으로 어떤 문제 가 동적 계획 을 사용 하여 해결 하기에 적합 합 니까?동적 계획 방법 을 응용 하여 해결 하기에 적합 한 최 적 화 된 문 제 는 두 가지 요 소 를 가 져 야 한다. 최 적 화 된 서브 구조 와 서브 문제 가 중첩 되 어야 한다.
최 우선 서브 구조:
동적 계획 방법 으로 최 적 화 된 문 제 를 해결 하 는 첫 번 째 단 계 는 가장 좋 은 구 조 를 묘사 하 는 것 이다.만약 한 문제 의 최 적 화 는 그 하위 문 제 를 포함 하 는 최 적 화 를 포함한다 면 우 리 는 이 문제 가 최 적 화 된 서브 구조 적 성격 을 가지 고 있다 고 말한다.그러나 이 때문에 최 적 화 된 부분 에 사용 되 는 모든 문 제 를 조심스럽게 살 펴 봐 야 한다.가장 좋 은 서브 구조의 성질 을 발굴 하 는 과정 에서 실제 적 으로 다음 과 같은 통용 모델 을 따 랐 다.

문제 가 가장 잘 풀 린 다 는 것 을 증명 하 는 첫 번 째 구성 부분 은 선택 을 하 는 것 이다. 이번 선택 은 하나 이상 해결 해 야 할 서브 문제 가 발생 할 것 이다.

주어진 문제 에 대해 가능 한 첫 번 째 선택 에서 어떤 선택 이 가장 좋 은 결 과 를 얻 을 수 있 는 지 이미 알 고 있다 고 가정 합 니 다.너 는 지금 이런 선택 이 구체 적 으로 어떻게 얻 었 는 지 에 관심 이 없다. 단지 이런 선택 을 이미 알 고 있다 고 가정 할 뿐이다.

가장 좋 은 선택 을 받 을 수 있 는 지 정 한 후에 이번 선택 에 어떤 하위 문제 가 발생 할 지, 그리고 하위 문제 공간 을 어떻게 가장 잘 묘사 할 지 확인 하 세 요.

원 문 제 를 구성 하 는 가장 좋 은 구성 부분 으로서 모든 하위 문제 의 해 는 그 자체 의 가장 좋 은 해 이다.

질문
동적 기획 방법 을 적용 하여 해답 을 구 하 는 가장 최 적 화 된 문제 가 갖 춰 야 할 두 번 째 성질 은 서브 문제 공간 이 반드시 충분 해 야 한 다 는 것 이다. 즉, 문제 의 귀속 알고리즘 은 똑 같은 서브 문 제 를 반복 적 으로 구 해 내 는 것 이지 새로운 서브 문 제 를 계속 생 성 하 는 것 이 아니다.일반적으로 서로 다른 하위 문제 의 총 수 는 입력 규모 의 다항식 함수 가 좋다.재 귀 알고리즘 이 같은 하위 문 제 를 반복 적 으로 풀 면 우 리 는 최적화 문제 가 중첩 자 문제 의 성질 을 가지 고 있다 고 말한다.
 
동적 계획 을 사용 하여 풀 수 있 는 문제 들:
강철 막대 절단:
이 문 제 는 동태 계획 방면 에서 가장 전형 적 인 문제 일 것 이다. 문 제 는 다음 과 같다. 한 회사 가 긴 강철 줄 을 구 매 하여 짧 은 강철 줄 로 절단 하여 판매 했다.절단 공정 자체 에 원가 지출 이 없다.회사 경영 진 은 가장 좋 은 절단 방안 을 알 고 싶 어 한다.만약 우리 가 i 인치 길이 의 강철 막대 기 를 파 는 가격 이 pi 라 는 것 을 안다 면, 강철 막대 의 길 이 는 모두 1 인치 이다.가격표 의 샘플 은 다음 과 같다.
길이 i
1
2
3　
4
5
6
7
8
9
10
가격
1
5
8
9
10
17
17
20
24
30
 
길이 가 n 인 강철 막대 와 가격 표를 정 하고 절단 방안 을 강구 하여 판매 수익 을 최대 로 합 니 다.길이 가 n 인치 인 강철 막대 의 가격 pn 이 충분 하 다 면 절단 이 전혀 필요 없 을 수도 있 습 니 다.
우 리 는 이러한 사고방식 을 이용 하여 이 문 제 를 생각 할 수 있다. 첫 번 째 절단 을 완성 한 후에 양쪽 강철 줄 을 두 개의 독립 된 강철 줄 절단 문제 의 실례 로 볼 수 있다.우 리 는 이 두 개의 관련 자 문 제 를 조합 하 는 가장 좋 은 해 제 를 통 해 가능 한 모든 두 개의 절단 방안 에서 수익 이 가장 큰 사람 을 선택 하여 우리 의 원래 문 제 를 구성 합 니 다. - 길이 가 n 인 강철 막대 절단 에 대한 가장 좋 은 해 제 를 구성 합 니 다.즉, 길이 가 n 인 강철 막대 의 최대 수익 은:
　　　　Rn = Max(Pn, R1+R(n-1), R2+R(n-2) ...... , R(n-1) + R1)
상기 산식 에서 Rn 은 길이 가 n 인 강철 막대 의 최대 수익 을 대표 한다. 예 를 들 어 R2 + R (n - 2) 은 길이 가 2 인 강철 막대 의 최대 수익 과 길이 가 n - 2 인 강철 막대 의 최대 수익 의 합 이다.그리고 우리 가 길이 가 n 인 강철 막대 의 가장 큰 수익 을 얻 는 방식 은 모든 가능 한 두 개의 절단 방안 에서 수익 이 가장 큰 사람 을 선택 하 는 것 이다.즉, 상기 일련의 최 적 화 된 조합의 최대 치 이다.
동적 계획 방법 을 사용 하여 가장 좋 은 강철 막대 절단 문 제 를 해결 하 는 데 는 두 가지 방법 이 있다.
메모 가 있 는 위 에서 아래로 방법:
이 방법 은 여전히 자 연 스 러 운 재 귀 형식 으로 과정 을 작성 하지만, 과정 은 모든 하위 문제 의 해 를 저장 합 니 다.하위 문제 의 풀이 가 필요 할 때 과정 은 먼저 감산 이 이 해 를 저장 한 적 이 있 는 지, 만약 그렇다면 저 장 된 값 을 직접 되 돌려 계산 시간 을 절약 했다.다음은 이러한 방법의 위조 코드 를 드 립 니 다.

 1 MEMOIZED-CUT-ROD(p, n)
 2 {
 3     let r[0...n] be a new array
 4     
 5     for(int i = 0; i <= n; i++)
 6     {
 7         r[i] = -∞;
 8     }
 9     
10     return MEMOIZED-CUT-ROD-AUX(p,n,r)
11 }
12 
13 MEMOIZED-CUT-ROD-AUX(p,n,r)
14 {
15     if(r[n] >= 0)
16     {
17         return r[n];
18     }
19     
20     if(n == 0)
21     {
22         q = 0;
23     }
24     else
25     {
26         q = -∞;
27         
28         for(int i = 1; i<= n; i++)
29         {
30             q = MAX(q, p[i] + MEMOIZED-CUT-ROD-AUX(p,n-i,r))
31         }
32     }
33     
34     r[n] = q;
35     
36     return q;
37 }

여기 서 먼저 보조 배열 r [0... n] 의 요 소 를 - 표시 로 초기 화 합 니 다.이것 은 사실 이 대응 하 는 값 을 '알 수 없 음' 으로 표시 하기 위 한 것 이다. 왜냐하면 우 리 는 수익 이 항상 마이너스 가 아니 라 는 것 을 확정 하기 때문에 이런 값 은 실제 적 으로 계산 되 지 않 았 음 을 확정 할 수 있다.MEMOIZED - CUT - OD - AUX (p, n, r) 과정 에서 필요 한 값 을 알 고 있 는 지 확인 하고, 알 고 있 으 면 바로 되 돌려 주지 않 으 면 필요 한 값 을 계산 한 다음 기록 합 니 다.28 ~ 31 줄 을 주의 하 세 요. 사실은 우리 가 전에 언급 한 사고 입 니 다. 모든 가능 한 두 개의 절단 방안 에서 수익 이 가장 큰 사람 을 선택 하 는 것 입 니 다.
 
아래 에서 위로 법:
이런 방법 은 일반적으로 하위 문제 의 '규모' 개념 을 적절하게 정의 해 야 하기 때문에 모든 하위 문제 의 해답 은 '더 작은' 하위 문제 의 해답 에 만 의존한다.따라서 우 리 는 하위 문 제 를 규모 에 따라 정렬 하고 작은 것 부터 큰 것 까지 순서대로 풀 수 있다.어떤 하위 문 제 를 풀 때, 그것 이 의존 하 는 더 작은 하위 문 제 는 모두 해결 되 었 고, 결 과 는 이미 보존 되 었 다.모든 하위 문 제 는 한 번 만 풀 어야 한다. 우리 가 그것 을 풀 때, 그것 의 모든 하위 문 제 는 이미 해결 되 었 다.다음은 이러한 방식 의 위조 코드 를 드 립 니 다.

 1 BOTTOM-UP-CUT-ROD(p,n)
 2 {
 3     let r[0...n] be a new array
 4     r[0] = 0;
 5     
 6     for(int j = 1; j <= n; j ++)
 7     {
 8         q = -∞;
 9         
10         for(i = 1; i <= j; i++)
11         {
12             q = max(q, p[i] + r[j-i]);
13         }
14         
15         r[j] = q;
16     }
17     
18     return r[n];
19 }

이런 방법 은 하위 문제 의 자연 순 서 를 채택 한다.
또한 필 자 는 이곳 을 처음 보 았 을 때 상기 방식 으로 우리 가 제시 한 길이 와 가격 의 표 에 대응 하 는 것 이 의문 이 었 다. 만약 에 길이 가 10 보다 크 면 어떻게 되 는 것 일 까?p [i] 는 error 가 색인 경 계 를 초과 했다 고 보고 할 것 입 니 다.실제로 위의 아래 에서 위로 올 라 가 는 방법 을 실제 적 으로 활용 하려 면 일부 논리 가 필요 하 다. 즉, p [] 배열 을 업데이트 하여 '더 큰' 규모 의 문제 에 부 딪 혔 을 때 이미 구 한 '더 작은' 규모 의 해 를 사용 할 수 있 도록 하 는 것 이다.
 
다음은 두 개의 LeetCode 의 동적 기획 제목 을 첨부 합 니 다.
출처: 버튼 (LeetCode), 전송 문
53. 최대 하위 순서 와
정수 배열 nums 지정 ，최대 와 연속 을 가 진 하위 그룹 (하위 그룹 은 최소 하나의 요 소 를 포함 합 니 다) 을 찾 아 최대 와 합 을 되 돌려 줍 니 다.
예시:
입력: [- 2, 1, - 3, 4, - 1, 2, 1, - 5, 4], 출력: 6 설명: 연속 서브 그룹 [4, - 1, 2, 1] 의 것 과 가장 큰 것 은? 6。

 1 public class Solution {
 2         public int MaxSubArray(int[] nums)
 3         {
 4             int maxValue = nums[0];
 5 
 6             for (int i = 1; i < nums.Count(); i++)
 7             {
 8                 if (nums[i - 1] > 0)
 9                 {
10                     nums[i] += nums[i - 1];
11                 }
12 
13                 maxValue = Math.Max(maxValue, nums[i]);
14             }
15 
16             return maxValue;
17         }
18 }

이 문 제 는 사실 한 가 지 를 이해 해 야 한다. 일단 납득 하면 위의 코드 를 이해 할 수 있다.즉, 위의 코드 는 이 배열 nums 의 모든 위치 에서 얻 을 수 있 는 최대 하위 트 리 의 합 을 구 한 것 입 니 다.다시 말 하면 index 가 0 이면 이 위치의 최대 와 nums [0] 이다.또한 index 가 3 이면 최대 합 은 Max (nums [0] + nums [1] + nums [2] + nums [3], nums [1] + nums [2] + nums [3], nums [2] + nums [3], nums[3])。
동적 기획 의 사고방식 으로 해석 하면 모든 위치 가 얻 을 수 있 는 최대 치 는 실제 적 으로 그 자체 의 값 과 그 이전 위치 가 얻 을 수 있 는 최대 치 와 밀접 한 관 계 를 가진다.
 
70. 계단 을 오르다
계단 을 오 르 고 있다 고 치자.필요 하 다 너 는 옥상 에 도착 할 수 있다.
매번 한 계단 이나 두 계단 을 올 라 갈 수 있다.당신 은 몇 가지 다른 방법 으로 옥상 까지 올 라 갈 수 있 습 니까?
주의: 주어진 n 은 정수 입 니 다.
예시 1:
입력: 2 출력: 2 해석: 옥상 까지 올 라 갈 수 있 는 두 가지 방법 이 있 습 니 다.1. 1 단계 + 1 단계 2. 2 단계 예시 2:
입력: 3 출력: 3 해석: 옥상 까지 올 라 갈 수 있 는 세 가지 방법 이 있 습 니 다.1. 1 단계 + 1 단계 + 1 단계 2. 1 단계 + 2 단계 3. 2 단계 + 1 단계

 1 public class Solution {
 2         public int ClimbStairs(int n)
 3         {
 4             if (n == 0)
 5             {
 6                 return 0;
 7             }
 8 
 9             if (n == 1)
10             {
11                 return 1;
12             }
13 
14             var n_Count = new int[n];
15 
16             n_Count[0] = 1;
17             n_Count[1] = 2;
18 
19             for (int i = 3; i <= n; i++)
20             {
21                 n_Count[i - 1] = n_Count[i - 2] + n_Count[i - 3];
22             }
23 
24             return n_Count[n_Count.Length - 1];
25         }
26 }

 
이 문제 의 사고방식 은 n 이라는 층 에 도달 하려 면 실제로 두 가지 방식 이 있 는데 그것 이 바로 n - 1 에서 1 단계 로 올 라 가 거나 n - 2 에서 2 단계 로 올 라 가 는 것 이다.따라서 n 층 에 도착 하 는 모든 방법의 합 은 n - 1 층 에 도착 하 는 모든 방법의 합 + n - 2 층 에 도착 하 는 모든 방법의 합 이다.
 
동적 계획 에는 아직도 많은 재 미 있 는 문제 가 있다. 예 를 들 어 가장 긴 공공 서브 시퀀스, 행렬 곱셈 등 은 지면 이 제한 을 받 으 면 기록 하지 않 는 다.