本文共 1083 字，大约阅读时间需要 3 分钟。

[DP解题] 剪绳子

【问题】给定一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]* k[1] * … *k[m]可能的最大乘积是多少？

示例1： 输入：8 输出：18

解释：当绳子的长度是8时，可以把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

[算法分析]

[算法设计]

package com.bean.algorithmbasic;public class CutRopeDemo {		/*	 * 算法设计	 * */	public static int cutRope(int length) {        if (length < 2) {            return 0;        }        if (length == 2) {            return 1;        }        if (length == 3) {            return 2;        }        int max = 0;        int res[] = new int[length];        res[0] = 2;        res[1] = 3;        for (int i = 4; i <= length; i++) {            max = 0;            for (int j = 2; j <= i / 2; j++) {                int r = res[j - 2] * res[i - j - 2];                if (max < r) {                    max = r;                    res[i - 2] = max;                }            }        }        max = res[length-2] ;        return max;    }	public static void main(String[] args) {		// TODO Auto-generated method stub		int RESULT= cutRope(10);		System.out.println("RESULT = "+RESULT);			}}

输出结果：

RESULT = 36

转载地址：http://udtdi.baihongyu.com/