동적 계획 문제 의 세 가지 간단 한 이해 - 줄 자 르 기

5692 단어 알고리즘
문제 설명
n 길이 의 끈 을 드 리 겠 습 니 다. 끈 을 정수 길이 의 m 단 (m, n 은 모두 정수, n > 1, m > 1) 으로 자 르 십시오. 각 끈 의 길 이 는 k [0], k [1]... k [m] 로 기록 하 십시오.실례 지만 k [0], k [1]... k [m] 가능 한 최대 곱 은 얼마 입 니까?예 를 들 어 끈 의 길이 가 8 일 때 우 리 는 그것 을 길이 가 각각 2, 3, 3 의 3 단 으로 자 르 는데 이때 얻 은 최대 곱 은 18 이다.
문제 해석
  • n 길이 의 밧줄 은 n - 1 회 까지 잘 린 다
  • m 번 째 를 자 른 후에 앞 m - 1 번 의 선분 곱 하기 를 이용 합 니 다. 즉, 우 리 는 마지막 으로 자 른 곳 을 약속 할 수 있 습 니 다. 그러면 우 리 는 앞의 m - 1 번 줄 의 최대 곱 하기
    • 만 필요 합 니 다.
    사고 분석.
  • 배열 cut [n] [n]
    • 만 들 기
  • cut [i] [j]: 모두 i 칼 을 잘 랐 고 마지막 칼 은 j 의 위치 에 떨 어 졌 다 는 뜻
  • i = 0 또는 j = 0 일 때 cut [i] [j] 는 의미 가 없다. 0 칼 을 자 르 거나 0 위 에 떨 어 지 는 것 은 의미 가 없 기 때문이다.
  • i = 1 일 때 한 칼 만 자 를 때 밧줄 은 반 으로 자 르 고 오른쪽 부분 은 잠시 상관 하지 않 으 며 왼쪽 부분의 길 이 는 j
    • 와 같다.
  • i = j 일 때 i 칼 을 잘 랐 는데 마지막 칼 이 i 위치 에 떨 어 졌 다. 즉, 모든 칼 은 1 단위 길이 로 잘 랐 기 때문에 cut [i] [i] = 1
  • 그러면 배열 의 다른 값 은 어떻게 확정 합 니까?
  • 예: cut [2] [3]: 2 번 째 칼 을 잘 랐 고, 2 번 째 칼 은 3 번 째 위치 에서 잘 랐 다
  • 그러면 첫 번 째 칼 은 두 번 째 위치 에서 자 를 수도 있 고 첫 번 째 위치 에서 자 를 수도 있다. 즉, 첫 번 째 칼 은 cut [1] [2] 와 cut [1] [1] 일 수도 있다. 우 리 는 * cut [1] [2] 만 비교 해 야 한다.×(3 - 2) 와 cut [1] [1]×(3 - 1) * * 의 값, 최대 값 은 cut [2] [3] 의 값
  • 다른 cut [i] [j] 에 대한 값 은 cut [i - 1] [j - 1]×(1) 부터 cut [i - 1] [i - 1]×(j - i + 1) 의 최대 치 입 니 다.

    • cut [i] [j] 할당 코드
    //cut    ，i=0 j=0    
        for(int i=1;i<n;i++){
            for(int j=i;j<n;j++){
                if(i==1)    cut[i][j]=j;
                else if(i==j)
                    cut[i][j]=1;
                else{
                    //        
                    int max = 0;
                    for(int t=j-1;t>=i-1;t--){
                        if(cut[i-1][t]*(j-t)>max)
                            max = cut[i-1][t]*(j-t);
                    }
                    cut[i][j]=max;
                }
            }
        }
    보위 안 (경 동 2017 필기시험 문제)
    [백준] 14890번 경사로

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage