java - 동적 기획 연습 1

동적 계획 은 매우 중요 한 알고리즘 으로 매우 중요 하 다.작년 에 채용 에 참 가 했 을 때 대부분의 필기시험 문 제 는 동태 적 인 계획 이 있 었 던 것 으로 기억한다.그때 젊 었 잖 아...  요 며칠 동안 동태 계획 을 잘 연습 해라.
       위 키 피 디 아 는 동태 계획 에 대한 정 의 는 동태 계획 은 문 제 를 나 누 어 문제 상태 와 상태 간 의 관 계 를 정의 하여 문 제 를 전달 하 는 방식 으로 해결 할 수 있 도록 하 는 것 이다.
       동적 계획 의 본질은 문 제 를 나 누고 문제 상태 와 상태 간 의 관 계 를 정의 하 는 것 이다. 문제 상 태 는 동적 계획 이 나 눌 수 있 는 서브 문제 이 고 상태 간 의 관 계 는 바로 동적 계획 서브 문제 간 의 관계 이 며 바로 우리 가 흔히 말 하 는 상태 전이 방정식 이다.
       솔직히 말 해서, 나 는 아직도 정의 에 대한 이해 가 매우 얕다.   문제 더 풀 어야 돼.  그냥 문제 내.
       먼저 가장 간단 한 것 이다. 동적 계획 은 int 형 배열 의 가장 긴 공공 서브 시퀀스 (서브 시퀀스 는 연속 되 지 않 고 서브 꼬치 가 연속 적 인 것) 문 제 를 해결 하 는 것 이다.
       예 를 들 어 배열 (1, 3, 2 곶) 이 있 는데 그의 가장 긴 서열 은 (1, 2 곶 이 고 길 이 는 2 이다.
       우선, 이 문 제 를 동태 적 인 계획 으로 할 수 있 는 지 를 분석 하 는 것 은 바로 이 문 제 를 작은 문제 로 나 눌 수 있 는 지 를 분석 하 는 것 이다.
       우선, 이 문 제 는 작은 문제 로 나 눌 수 있 습 니 다. 배열 sums {0, 1, 2. n} 에 있어 서 그의 최 장자 서열 을 구 할 수 있 습 니 다. 먼저 sums {0, 1, 2, n - 1] 의 최 장자 서열 을 구 한 다음 에 sums 의 최 장자 서열 을 구 할 수 있 습 니 다.
        해체 분자 문 제 는 분명히 많은 사람들 이 재 귀 를 생각 하고 있 을 것 이다. 동태 계획 이 해결 할 수 있 는 문 제 는 일반적으로 재 귀적 으로 도 해결 할 수 있 지만 동태 계획 의 장점 은 큰 문제 의 해결 이 작은 문제 의 해결 에 의존 할 때 동태 계획 은 상태 보호 배열 이 있어 서 이미 해 결 된 작은 문 제 를 보관 하 는 것 이다. 재 귀 처럼 여러 번 중복 계산 을 하지 않 고 가장 전형 적 인 것 은피 보 나 스 수열 이 야.
         P (i) 가 배열 sums (0, 1, 2... i 곶 의 가장 긴 하위 서열 의 크기 라 고 가정 하면 P (N) 의 값 은 얼마 입 니까? 우선 P (N) 는 무엇 에 의존 합 니까? P (N) 는 P (0), p (1)... p (n - 1) 에 의존 합 니 다. 이 럴 때 하나의 배열 M (i) 이 배열 sums (0, 1, 2. i 곶 의 가장 긴 하위 서열 크기 가 P (i) 일 때 이 가장 긴 하위 서열 에서 요소 의 최대 치 를 저장 해 야 합 니 다. 그러면 P (i) 로M (i) 을 바탕 으로 P (N) 가 P (i) 에 의존 하 는 상황 에서 의 값 을 계산 할 수 있다.
        sums [n] > M (i) 이면 P (n) = p (i) + 1, M (n) = sums [n]
                              그렇지 않 으 면: P (n) = p (i), M (n) = M [i]
        말 만 하면 이해 하기 어 려 울 수도 있 습 니 다. 저 는 이해 하기 어 려 운 문 제 를 비교적 가 벼 운 예 로 연산 하 는 것 을 좋아 합 니 다.
         예 를 들 어 배열 (1, 3, 2 곶) 의 경우 초기 상황 에서 P (0) = 1, M (0) = 1 (이것 은 설명 할 필요 가 없 겠 지. 초기 상황 에서 배열 (1 곶 에 있어 최 장 자 서열 의 크기 는 1 이 고 최 장 자 서열 에서 최대 요 소 는 1) 이다.
         그리고 P (1), 이때 n = 1, i = 0 을 구하 고 sums [1] 와 M (0) 의 크기 를 비교 한 결과 sum [1] > M [0] 을 발 견 했 기 때문에 P (1) = p (0) = 1, m (1) = m (0) = 1;
         그리고 i = 0 에 따라 P (2) 를 판단 한다.
         우선 sums [n] > M (i) 에 따라 p (2) = p (i) + 1 = 2, M (2) = sums [2] = 3 을 알 수 있 습 니 다. 이것 이 결과 입 니 다!
         논 리 는 이렇다. p (n) 를 구 할 때 각각 (0, 1, 2... n - 1) 에 근거 하여 가능 한 모든 p (n) 값 을 구하 고 가장 큰 것 을 취하 면 된다. 개인 적 으로 이렇게 묘사 하 는 것 이 수학 공식 묘사 보다 좀 더 잘 보일 것 이 라 고 생각한다...
       마지막 으로 코드 를 올 립 니 다.

/**
 * DPTest :       
 * 
 * @author xuejupo [email protected]
 * 
 *         create in 2016-1-14   6:59:34
 */

public class DPTest {

	/**
	 * main:
	 * 
	 * @param args
	 *            void     
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(dpIncreasing(new int[] { 1, 2, 3, 4, 6, 7, 3, 8 }));
	}

	/**
	 * dpIncreasing:                  int            ， ｛1，2，3，4，6，2，3，8｝，  6
	 * 
	 * @param nums
	 * @return int     
	 */
	private static int dpIncreasing(int[] nums) {
		//     
		if (nums == null || nums.length == 0) {
			return 0;
		}
		//     ，              
		int[] help = new int[nums.length];
		//    
		help[0] = 1;
		//     ，   j            
		//  ｛1，2，3，4，6，2，3，8｝，   ｛1，2，3，4，6｝     6
		int[] help1 = new int[nums.length];
		//    
		help1[0] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			//   i           
			//       ：max(help(0->i-1)+1)
			int max = 0;
			//         ：  i      ，  1   i-1               
			for (int j = 0; j < i; j++) {
				int maxTemp = 0;
				if (help1[j] < nums[i]) {
					maxTemp = help[j] + 1;
				} else {
					maxTemp = help[j];
				}
				if (max < maxTemp) {
					max = maxTemp;
					help1[i] = Math.max(nums[i], help1[j]);
				}
			}
			help[i] = max;
		}
		return help[nums.length - 1];
	}
}

 결과:

7