40.剣指Offerの縄切り

目次

テーマ説明:

2.解題構想

3.プログラミングインプリメンテーション(Java):

1タイトル説明:
  長さnのロープを1本あげます.ロープを整数長のmセグメント(m、nは整数、n>1かつm>1、m<=n)に切ってください.各セグメントのロープの長さはk[1]、...、k[m].k[1]x...xk[m]の最大積はいくらですか.例えば、ロープの長さが8の場合、私たちはそれを長さがそれぞれ2、3、3の3セグメントに切って、このとき得られる最大積は18です.
入力説明:1つの数nを入力し、意味は問題面を参照してください.(2<=n<=60)出力記述:出力答え.例:入力8、出力18
2.問題の解き方
この問題を解決するには2つの異なる方法がある.

動的計画:時間複雑度O(n^2);空間複雑度:O(n).第1のナイフを切る場合、n−1の選択があり、すなわち、切断された第1のロープの長さは1,2,3,...,n−1である可能性がある.従ってf(n)=max(f(i)*f(n−i))であり、0再帰的には重複するサブ問題が多いため(これも問題を解くために動的に規定されたフラグを用いることができる)ため、多くの不要な繰り返し計算が可能である.より良い方法は、下から上へ計算し、前の計算の結果を記憶し、計算後の結果が前の結果に用いられる場合、前の結果を直接取り出して使用すれば、大量の繰り返し計算プロセスを回避することができる.

貪欲アルゴリズム:時間複雑度O(1);空間複雑度O(1)n>=5のとき、2(n−2)>nおよび3(n−3)>n.すなわち、ロープの残りの長さが5以上のとき、長さが3または2のロープセグメントに切る.また、n>=5のとき、3(n−3)>=2(n−2)のとき、できるだけ長さが3のロープセグメントを多く切るべきである.

3.プログラミング実装(Java):

public class cutRope_40 {
    public static void main(String[] args) {
        System.out.println(cutRope(9));
    }

    //    
    public static int cutRope(int target) {
        if (target < 2)
            return 0;
        if (target == 2)
            return 1;
        if (target == 3)
            return 2;
        int[] result = new int[target + 1];
        result[0] = 0;
        result[1] = 1;
        result[2] = 2;
        result[3] = 3;
        int max = 0;
        for (int i = 4; i <= target; i++) {
            for (int j = 1; j <= i / 2; j++) {
                int temp = result[j] * result[i - j];
                if (max < temp) {
                    max = temp;
                }
                result[i] = max;
            }
        }
        return max;
    }

    //    
    public static int cutRope(int target) {
        if (target < 2)
            return 0;
        if (target == 2)
            return 1;
        if (target == 3)
            return 2;
        //       3
        int threeOfRope = target / 3;
        //            4   ，        3    ，
        //                 2   ，  2X2>3X1
        if (target - threeOfRope * 3 == 1)
            threeOfRope--;
        int twoOfRope = (target - threeOfRope * 3) / 2;
        return (int) (Math.pow(3, threeOfRope) * Math.pow(2, twoOfRope));
    }
}