給你一根長度為n的繩子慰枕，請把繩子剪成整數(shù)長度的m段(m具则、n都是整數(shù)，n>1并且m>1)具帮，每段繩子的長度記為k[0],k[1]...k[m-1]博肋。
請問k[0] × k[1] × ... × k[m-1]可能的最大乘積是多少？
例如蜂厅，但繩子的長度是8時匪凡，我們把它剪成長度分別為2,3,3的三段，此時得到的最大乘積是18掘猿。

示例1：
輸入：2
輸出：1
解釋：2 = 1 + 1,1 × 1 = 1
示例2：
輸入：10
輸出：36
解釋：10 = 3 + 3 + 4病游， 3 × 3 × 4 = 36

解題思路：動態(tài)規(guī)劃
對于的繩子的長度 n，當 n ≥ 3 時术奖，可以拆分成至少兩個正整數(shù)繩長的和礁遵。令k是拆分出的第一個正整數(shù)，
則剩下的部分是 n-k采记，n?k 可以不繼續(xù)拆分佣耐，或者繼續(xù)拆分成至少兩個正整數(shù)的和。
由于每個正整數(shù)對應的最大乘積取決于比它小的正整數(shù)對應的最大乘積唧龄，因此可以使用動態(tài)規(guī)劃求解兼砖。
創(chuàng)建數(shù)組dp,其中dp[i]表示將正整數(shù)i拆分成至少兩個正整數(shù)的和之后，這些正整數(shù)的最大乘積既棺。
特別地讽挟，繩子長度不能為0，如果繩子長度為1不能剪丸冕，繩子長度為2只能剪成兩段耽梅，因此，dp[0] = 0, dp[1] = 1, dp[2] = 2
當 i ≥ 2 時胖烛，假設對正整數(shù) i 拆分出的第一個正整數(shù)是 j（1 ≤ j < i）眼姐，則有以下兩種方案：
將 i 拆分成 j 和 i-j 的和，且 i-j 不再拆分成多個正整數(shù)佩番，此時的乘積是 j×(i?j)众旗；
將 i 拆分成 j 和 i-j 的和，且 i-j 繼續(xù)拆分成多個正整數(shù)趟畏，此時的乘積是 j×dp[i?j]贡歧。
因此，當 j 固定時，有 dp[i]=max(j×(i?j),j×dp[i?j])利朵。由于 j 的取值范圍是 1 到 i-1律想，需要遍歷所有的 j 得到 dp[i] 的最大值，
因此可以得到狀態(tài)轉移方程如下：dp[i]=max{max(j×(i?j),j×dp[i?j])}
最終得到 dp[n] 的值即為將正整數(shù) n 拆分成至少兩個正整數(shù)的和之后哗咆，這些正整數(shù)的最大乘積蜘欲。

public class CuttingRope {
    public static void main(String[] args) {
        int n = 10;
        System.out.println(cuttingRope(n));
    }

    private static int cuttingRope(int n){
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++){
            int maxResult = 0;
            for (int j = 1; j < i; j++){
                maxResult = Math.max(maxResult,Math.max(j * (i - j),j * dp[i - j]));
            }
            dp[i] = maxResult;
        }
        return dp[n];

    }


}