剑指 Offer 14- I. 剪绳子

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，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
提示：

2 <= n <= 58

思路

这是一个明显的几何均值不等式
$$
\frac{n_1 + n_2 + … + n_a}{a} \geq \sqrt[a]{n_1 n_2 … n_a}
$$
这是高中题，结果我完全没有印象了，怀疑我的高中是怎么上的。

推论一：将绳子 以相等的长度等分为多段 ，得到的乘积最大。

当长度相等即n1=12=..=na的时候取最大值

推论二： 尽可能将绳子以长度 3 等分为多段时，乘积最大。

真的想不到！

还是用贪心算法吧

证明过程

https://zhuanlan.zhihu.com/p/103989923

我感觉证明过程中的柯西归纳法比较容易理解，没有涉及到太多的理论知识，只是设计的非常巧妙

  1. 先得出在2的n次幂个数的情况下，条件是成立的
  2. 然后从X(n+1)开始去一个特殊值，为了后面的推到公式使用
  3. 最后代入公式发现，X1到Xn这个公式的租后推导结果与X(n+1)及后面的数值没有关系，所以对任意的数从X1到Xn都是成立的

实现

递归

递归的主要思想是，看这个题目能不能拆分出一个方程，结果的依赖性。

例如本到题目：首先我们对n长度的绳子，先从i的位置切一刀，那么如果要达到总长度的最大值，后续有两种选择：切还是不切。

递归的终止条件就是：n =2或n=1的时候，最大的长度为1，那么求总长度最大，后续长度就是（n-i），在切和不切中选取一个最大值，然后，因为递归是遍历所有的可能，所以我们必须要记录每次结果中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static class Solution3 {
    public int cuttingRope(int n) {
        if (n == 2 || n == 1 ){
            return 1;
        }
        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            // 当前记录绳子的最大值，和在i位置剪一刀后绳子可能的最大值进行比较
            res = Math.max(res,Math.max(i * (n -i),i * cuttingRope(n - i)));
        }
        return res;

    }
}

记忆化递归

具体思路参考斐波那契数列

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
private static class Solution4 {
        public int cuttingRope(int n) {

            if (n == 2 || n == 1 ){
                return 1;
            }
            int[] ropes = new int[n+1];
            ropes[0] = 0;
            ropes[1] = 1;
            ropes[2] = 1;
            return myCuttingRope(n,ropes);

        }

        private static int myCuttingRope(int n, int[] ropes){
            if (n < 2 || ropes[n] > 0){
                return ropes[n];
            }
            int res = 0;
            for (int i = 2; i < n + 1; i++) {
                res = Math.max(res,Math.max(i * (n -i),i * myCuttingRope(n - i,ropes)));
            }

            return ropes[n] = res;
        }
    }

动态规划

因为我们是要找的最优解，这种一般就是典型的动态规划题目，而且针对本题，动态规划也是最容易理解的

动态规划其实就是记忆化递归的逆序，

动态规划的方程

假设前面取的长度为j，那么后面取的长度（i-j）分为两种情况

  1. 后面的长度不拆分

    j * (i - j)

  2. 后面的长度还是需要拆分

    j * dp[i - j]

$$
ropes[i] = max(ropes[i], max(j * (i - j), j * ropes[i - j]))
$$

动态规划的初始条件和边界条件

初始化条件：ropes[2] = 1

边界条件：对长度为n的绳子，切割了n次

计算顺序

  • 初始条件： ropes[2] = 1;
  • 然后计算f[3]，f[4]，……，f[n]
  • 当我们计算到f[n]时候，f[i]，f[i-j]都已经得出结果了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static class Solution {
    public int cuttingRope(int n) {
        // 动态规划基本，定义一个数组，记录每次的数据结果
        int[] ropes = new int[n + 1];
        ropes[2] = 1;
        for (int i = 3; i < n + 1; i++) {
            for (int j = 2; j < i; j++) {
                
                ropes[i] = Math.max(ropes[i], Math.max(j * (i - j), j * ropes[i - j]));
            }
        }
        return ropes[n];
    }
}

贪心算法

贪心算法主要是公式的推导，一般是尝试公式的正确性（或者用数学证明，但是写算法的时候一般都不需要证明）

这个就是上面的思路过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static class Solution2 {
    public int cuttingRope(int n) {
        // 如果n < 4 ，直接返回就行
        if (n < 4) {
            return n - 1;
        }
        int res = 1;
        // n > 4的时候，每次递减3，如果剩余的数小于5，就不进行查分，直接全部返回
        while (n > 4) {
            n = n - 3;
            res *= 3;
        }
        return res * n;
    }
}

博客首先发布于：

https://lvxiaoyi.top/