剪绳子 java

墨蓝 2022-05-14 10:55 162阅读 0赞

题目还原：  
给你一根长度为n的绳子，请把绳子剪成m段，记每段绳子长度为k\[0\],k\[1\]...k\[m-1\],求k\[0\]*k\[1\]...*k\[m-1\]的最大值。已知绳子长度n为整数，m>1(至少要剪一刀，不能不剪)，k\[0\],k\[1\]...k\[m-1\]均要求为整数。例如，绳子长度为8时，把它剪成3-3-2，得到最大乘积18；绳子长度为3时，把它剪成2-1，得到最大乘积2。

分析：要求的是乘积的最大值，因此可以定义一个函数f(n)表示长度为n的绳子剪成若干段后各段乘积的最大值。如果我们剪了1刀，那么可以有n-1种可能（1，2，3，...n-1）；剪了2刀，剩下的可以有n-2种可能；推广到i刀，可以有n-i种可能。即f(n) = max(f(i)\*f(n-i))。这个类似于斐波那契数列，但是在斐波那契数列中我们都知道，按照原始定义的形式并不是一个好方法，用迭代法可以获得更好的性能，因此，这里也采用迭代法。即剑指offer中说的从下而上的顺序，先得到f(2),f(3)，再得到f(4),f(5)，...一直到f(n)。下面重点就是解决max(f(i)\*f(n-i))，可以在循环中，用类似选择排序的思想，用一个临时变量记录当前最大值，然后后面的依次和最大值进行比较，循环结束后，最大值即当前长度的最大乘积。代码如下：

public class 剪绳子 {
        public static int maxAfterCutting(int length) {
            if (length < 2) {
                return 0;
            }
            if (2 == length) {
                return 1;
            }
            if (3 == length) {
                return 2;
            }
            int[] products = new int[length + 1];  // 将最优解存储在数组中
            // 数组中第i个元素表示把长度为i的绳子剪成若干段之后的乘积的最大值
            products[0] = 0;
            products[1] = 1;
            products[2] = 2;
            products[3] = 3;
            int max = 0;
            for (int i = 4; i <= length; i++) {  //i表示长度
                max = 0;
                for (int j = 1; j <= i / 2; j++) {  //由于长度i存在（1，i-1）和（i-1，1）的重复，所以只需要考虑前一种
                    int product = products[j] * products[i - j];
                    if (product > max) {
                        max = product;
                    }
                }
                products[i] = max;
            }
            return products[length];
        }
    
    }