剣指offer-14.ロープを切る——分析とコード(Java)

剣指offer——14.ロープを切る——分析とコード[Java]

一、テーマ

二、分析及びコード

1. 動的計画

(1)考え方

(2)コード

(3)結果

2. 貪欲アルゴリズム

(1)考え方

(2)コード

(3)結果

三、その他

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

  1  
  ：8  
  ：18  

二、分析及びコード
1.動的計画
(1)考え方
長さlのロープについては、切り取った最初のセグメントを単独で考慮することができる.第1セグメントの長さがjである場合、現在のせん断法における最大積はj*[長さがl−jロープの最大積](状態遷移方程式)である.従って、第1段の長さを遍歴すると、その長さのロープの最大積が得られる.途中でより短いロープの結果が使われるため、計算時に対応する結果を保存する配列を設計することができます.注意点:1)長さが2、3のロープは、最終結果(0刀を切ることができない)と中間結果(0刀を切ることができる)とでは答えが異なり、単独で処理する必要がある.2)第1段の長さが1の場合、1節の縄の長さを浪費したことに相当し、結果は最も大きな解ではなく、直接2から遍歴すればよい.3)第1セグメント長>ロープ長の半分の場合、分割方式は対称に繰り返し、計算しなくてもよい.
(2)コード

public class Solution {
    public int cutRope(int target) {
        if (target < 2)
            return 0;
        if (target < 4)
            return target - 1; // 2 -> 1, 3 -> 2
        int[] mult = new int[target + 1];
        mult[2] = 2;
        mult[3] = 3;
        for (int i = 4; i <= target; i++) {
            int half = i >> 1;
            for (int j = 2; j <= half; j++) {
                mult[i] = Math.max(mult[i], mult[j] * mult[i - j]);
            }
        }
        return mult[target];
    }
}

(3)結果
実行時間:17 ms、メモリ消費量:9692 k.
2.貪欲アルゴリズム
(1)考え方
数学的方法の計算分析に基づいて、最適な剪断法は:1)ロープの長さ≧5の場合、できるだけ多くの長さ3のロープを剪断することである.2)ロープ長=4の場合、切らない(または2段長2のロープに切る、両者の結果は同じ).上記の方法に基づいて最大積を直接計算することができる.
(2)コード

public class Solution {
    public int cutRope(int target) {
        if (target < 2)
            return 0;
        if (target < 4)
            return target - 1; // 2 -> 1, 3 -> 2
        if (target % 3 == 0)
            return (int)Math.pow(3, target / 3);
        if (target % 3 == 1)
            return (int)Math.pow(3, target / 3 - 1) * 4;
        return (int)Math.pow(3, target / 3) * 2;
    }
}

(3)結果
実行時間:21 ms、メモリ使用量:9712 k.
三、その他
しばらくありません.