검지offer 면접문제:14 밧줄 자르기(Java 버전)

제목.
길이가 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이다.
사고의 방향
동적 계획 해법
함수 F (n) 를 먼저 정의하면 길이가 n인 밧줄이 몇 개의 세그먼트로 자른 후 각 세그먼트의 길이 곱셈의 최대값을 나타냅니다.첫 번째 칼을 자를 때 우리는 n-1의 가능한 선택이 있다. 즉, 첫 번째 단락의 밧줄의 길이가 1,2,3,..., n-1일 수 있기 때문에 F(n)=max(F)*F(n-i)), 그 중에서 0
이것은 위에서 아래로의 귀속 공식이다.귀환에는 중복된 하위 문제가 많기 때문에 대량의 불필요한 중복 연산이 있을 것이다.상술한 문제를 피하기 위해서, 우리는 귀속을 채택하지 않고, 아래에서 위로 순서대로 계산한다. 즉, 먼저 F (1) 를 계산하고, 이어서 F (2) 를 계산하고, F (n) 를 얻을 때까지 계산한다.
밧줄의 길이가 2일 때는 두 단락의 길이가 모두 1인 것만 잘라야 하기 때문에 f(2)=11=1, 밧줄의 길이가 3일 때는 각각 1, 2의 두 단락 또는 길이가 1의 세 단락으로 잘라낼 수 있다. 왜냐하면 111=1<12=2이기 때문에 f(3)=2
코드 구현

 public static int maxProductAfterCutting_solution1(int length)
    {
    //    0、1、2、3         
        if(length<2)
        {
            return 0;
        }
        if(length==2)
        {
            return 1;
        }
        if(length==3)
        {
            return 2;
        }
        //products   i         i                    
        //i>=4       
        int[] products=new int[length+1];
        //             ，     i>=4   
        products[0]=0;
        products[1]=1;
        products[2]=2;
        products[3]=3;
        int max=0;
        for(int i=4;i<=length;i++)
        {
            max=0;
            //     i                    
            for(int j=1;j<=i/2;j++)
            {
                int product=products[j]*products[i-j];
                if(max<product)
                {
                    max=product;
                }
            }
            products[i]=max;
        }
        max=products[length];
        return max;

    }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

알고리즘 1000 개 노크 #6. ZigZag Conversion

Problem 문제는 에서 빌리고 있지만, 예제를 보는 한 Paypal의 인터뷰에서 출제 된 것이 있다고 추측됩니다. Solution 지그재그에 나열한 다음 각 행을 t0 , t1 , t1 . 파이썬 버전 코드: 계...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

검지offer 면접문제:14 밧줄 자르기(Java 버전)

좋은 웹페이지 즐겨찾기