剑指offer——剪绳子

题目:
给你一根长度为n的绳子,请把绳子剪成m段 (m和n都是整数,n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少?
例如,当绳子的长度为8时,我们把它剪成长度分别为2,3,3的三段,此时得到的最大乘积是18.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class 剪绳子 {
    public static int jsz2(int length) {
        if(length < 2) {
            return 0;
        }
        if(length == 2) {
            return 1;
        }
        if(length == 3) {
            return 2;
        }
        //length大于5,则尽可能多的剪长度为3的
        int time3 = length/3;
        //如果剪3的剩余1,也就是存在剩4的情况,则拿出一个3
        if(length - time3*3 == 1) {
            time3 -= 1;
        }
        //剪3的次数等于剩余长度/2
        int time2 = (length - time3*3)/2;
       
        return (int)((Math.pow(3, time3))*(Math.pow(2, time2)));
    }
    public static int jsz1(int length) {
        if(length < 2) {
            return 0;
        }
        if(length == 2) {
            return 1;
        }
        if(length == 3) {
            return 2;
        }
        // 将最优解存储在数组中
        int[] res = new int[length+1];
        // 数组中第i个元素表示把长度为i的绳子剪成若干段之后的乘积的最大值
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        res[3] = 3;
        int max = 0;
        // 求出所有可能的f(j)*f(i-j)并比较出他们的最大值
        for(int i = 4;i <= length;i++) {
            max = 0;
            for(int j = 1;j <= i/2;j++) {
                int re = res[j]*res[i-j];
                if(max < re) {
                    max = re;
                }
                res[i] = max;
            }
        }
        max = res[length];
        return max;    
    }

    public static void main(String[] args) {
        System.out.println(jsz1(8));
        System.out.println(jsz2(8));
    }

}
0 条评论
发表一条评论