규방 의 최대 곱 하기 분석

원제
밧줄 한 가닥 의 길 이 는 n 미터 이다.그것 을 몇 단락 으로 자 르 면 각 단락 의 길 이 는 정수 이다.각 단락 의 밧줄 사이 의 곱셈 이 가장 클 수 있 도록 절단 법 을 제시 해 주 십시오.주의해 라, 적어도 한 번 썰 어야 한다.
분석 하 다.
이 문 제 는 어떻게 한 걸음 한 걸음 분석 합 니까?몇 단락 을 자 르 든 첫 번 째 단락, 두 번 째 단락... 등등 이 있다.1 단의 길 이 는 어떤 선택 이 있 나 요?1, 2, 3 이 될 수 있 습 니 다. n - 1 까지 (적어도 잘라 야 합 니 다), 우 리 는 max 를 사용 합 니 다.prod (n) 는 길이 가 n 인 밧줄 의 절단 법 에서 곱 하기 가 가장 큰 값 을 나타 낸다.그러면:

1.        1 ，      ：max(1×max_prod(n-1), 1×(n-1)) 2.        2 ，      ：max(2×max_prod(n-2), 2×(n-2)) 3. … 4.        n-1 ，      ：(n-1)*1=n-1

위 에 왜 맥 스 를 뽑 는 거 죠?주의 하 세 요. 문제 중의 요 구 는 적어도 잘라 야 합 니 다.이렇게 위의 분석 에서 알 수 있 듯 이 재 귀적 표현 식 은 첫 번 째 줄 의 길 이 를 i 로 설정 하고 수치 범 위 는 [1, n - 1] 이 며 모든 i 에 대해 최대 곱 하기: max (i) 가 있다.×(n-i),i×max_prod(n-i))。그리고 모든 i 에 대해 가장 큰 값 을 구 하 는 것 이 최종 답 이다.
이 문 제 는 여기까지 인가요?우리 가 이전에 분석 한 학우 들 을 보면 곧 생각 할 수 있 을 것 이다. 더 나 아가 이런 문제 들 중 중복 되 는 것 이 있 는 지, 있 으 면 동적 기획 방법 으로 알고리즘 개선 을 할 수 있다.반복 적 인 귀속 자 문제 가 있 는 지 확인 하 는 가장 좋 은 방법 은 종이 에 귀속 나 무 를 그린 다음 에 중복 되 는 귀속 자 문제 가 있 는 지 확인 하 는 것 이다.한눈 에 알 수 있어.이 문 제 는 비교적 뚜렷 하 다. 학생 들 은 종이 에 그림 을 그리고 연습 을 해 볼 수 있다.
기왕 우리 가 중 복 된 귀속 자 문 제 를 명 확 히 했 으 니, 그 다음은?동태 기획 주 제 를 전문 적 으로 배 운 친구 들 은 이런 말 을 기억 할 것 이다. '위 에서 아래로 문 제 를 분석 하고 아래 에서 위로 문 제 를 해결 하 자' 는 말 은 대체적으로 비슷 하고 원래 말 이 아 닐 수도 있다.아래 에서 위로 문 제 를 해결 하 는 것 은 작은 문 제 를 먼저 해결 한 다음 에 이런 작은 문제 의 결과 에 따라 한 무더기 의 문 제 를 해결 하고 전체 문 제 를 해결 할 때 까지 순서대로 해결 하 는 것 이다.

1.        1   ，  ，    2.        2   ，   ，max_prod[2]=1×1 3.        3   ，   ，max_prod[3]=1×2 4.        4   ，            ，  ，      2  。 5. …

이것, 상태 전이 방정식 은 maxprod[i]=max((i-j)×j, j×max prod [i - j]), 그 중 j 의 범 위 는 [1, i / 2] 입 니 다.분명히 동적 기획 방법의 시간 복잡 도 는 O (n ^ 2) 이 고 공간 복잡 도 는 O (n) 이다.

int maxMult(int n)
{
	vector<int> dp(n+1,1);
	int len,i;
	for (len = 3;len <= n;len++)
	{
		for (i = 1;i < len;i++)
		{
			int t = max(dp[len-i],len-i)*i;//dp[len-i]    (len-i)，  dp[len-i]     len-i         ， len-i      ，     
			dp[len] = max(dp[len],t);
		}
	}
	return dp[n];
}

이 문 제 는 여기까지 만 해도 괜찮다.그러나 아직 끝나 지 않 았 다. 이 문 제 는 더욱 교묘 한 방법 이 있다.웨 이 보 에서 어떤 학생 들 은 다음 과 같은 방법 을 제시 했다. 길이 n 을 3x + 2y = n 으로 표시 하고 3 을 가능 한 한 많이 표시 해 야 한다. 이런 3 ^ x + 2 ^ y 가 가장 크다.찬탄 하지 않 을 수 없다. 이것 은 확실히 매우 교묘 한 방법 이다.여러분 은 예 를 통 해 몇 가 지 를 검증 할 수 있 습 니 다.왜 3 이랑 2 밖 에 없 지?길이 가 4 인 게 2 예요.×2, 5 이상 이면 모두 3x + 2y 로 분해 할 수 있 으 며 3 ^ x + 2 ^ y > 5 이상 의 숫자 로 분해 할 수 있 습 니 다.이 문 제 는 정수 가 요구 되 는데, 이 제한 을 취소 하면?사고의 방향 을 넓 히 고 하 나 를 보면 열 을 안다. 여러분 들 은 많이 생각 하 시기 바 랍 니 다.