검지offer 면접문제 14 밧줄 자르기(동적 기획과 탐욕 알고리즘)

10898 단어 
#include
#include

using namespace std;

//    
int maxProductAfterCutting_soution(int length)
{
	if (length < 2)
		return 0;
	if (length == 2)
		return 1;
	if (length == 3)
		return 2;
	int* products = new int[length + 1];
	//      products      ，       4 ，f(5) = f(3)*f(2) = 2*3 ;
	products[0] = 0;
	products[1] = 1;
	products[2] = 2;
	products[3] = 3;
	int max = 0;
	for (int i = 4; i <= length; ++i)
	{
		max = 0;
		for (int j = 0; j <= i / 2; ++j)
		{
			int product = products[j] * products[i - j];
			if (max < product)
				max = product;
			products[i] = max;
		}
	}
	max = products[length];
	delete[] products;
	return max;
}

//    

int maxProductAfterCutting_soution2(int length)
{
	if (length < 2)
		return 0;
	if (length == 2)
		return 1;
	if (length == 3)
		return 2;

	int timesOfthree = length / 3;
	if (length - timesOfthree * 3 == 1)
		timesOfthree -= 1;
	int timesOftwo = (length - timesOfthree * 3) / 2;
	return (int)(pow(3, timesOfthree))*(int)(pow(2, timesOftwo));
	
}



int  main()
{
	int max1 = 0;
	int max2 = 0;
	max1 = maxProductAfterCutting_soution(50);
	max2 = maxProductAfterCutting_soution2(50);
	cout << max1 << " " << max2;
	cin.get();
	return 0;
}

코드에서 그룹 제품에 대한 초기 값을 주의해야 합니다.
js 1 천만 개의 데이터 정렬 을 처리 하고 페이지 가 멈 추 지 않 습 니 다.
js 텍스트 상자 의 입력 을 금지 하 는 일반적인 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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