[剑指 Offer 第 2 版第 14 题] “剪绳子”做题记录

第 14 题：剪绳子

说明：同 LeetCode 343 题。

给你一根长度为 $n$ 的绳子，请把绳子剪成 $m$ 段（ $m$ 、 $n$ 都是整数， $2 \\le n \\le 58^2$ 并且 $m \\ge2$ ）。

每段的绳子的长度记为 k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？

例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

样例：

输入：8

输出：18

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

分析：这道题在牛客网上没有 online judge ，我们可以去完成 LeetCode 上第 343 题检验自己的代码是否编写正确。

动态规划。关键在于画出树形结构图。

状态：dp[i]，这个状态就是题目中要我们求的。把整数 i 至少分割成 $2$ 个部分，各个部分都大于 $0$ ，它们的乘积。

状态转移方程：用 j 遍历 1，2，…, i -1 ，要么分割成两部分：i - j 和 j，要么是 j 和 dp[i-j]，取最大者。

Python 代码：dp[0] 这个位置没有使用

  class Solution(object):
        def maxProductAfterCutting(self, length):
            """
            :type length: int
            :rtype: int
            """

            assert length > 1

            dp = [0 for _ in range(length + 1)]

            dp[1] = 1

            for i in range(2, length + 1):
                for j in range(1, i):
                    dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
            return dp[length]

Java 代码：使用动态规划

  class Solution {
        public int integerBreak(int n) {
            if (n <= 1) {
                return 1;
            }
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                int max = 0;
                for (int j = 1; j < i; j++) {
                    max = max3(max, j * (i - j), j * dp[i - j]);
                }
                dp[i] = max;
            }
            return dp[n];
        }

        private int max3(int num1, int num2, int num3) {
            return Integer.max(Integer.max(num1, num2), num3);
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            int integerBreak = solution.integerBreak(8);
            System.out.println(integerBreak);
        }
    }

Java 代码：使用贪心算法

  class Solution2 {
        public int integerBreak(int n) {
            if (n <= 2) {
                return 1;
            }
            if (n == 3) {
                return 2;
            }
            if (n == 4) {
                return 4;
            }
            // 接下来就是 n >= 5 的时候的逻辑了
            int res = 1;
            while (n > 4) {
                res *= 3;
                n -= 3;
            }
            res *= n;
            return res;
        }

        public static void main(String[] args) {
            Solution2 solution2 = new Solution2();
            int integerBreak = solution2.integerBreak(8);
            System.out.println(integerBreak);
        }
    }

LeetCode 343 题：整数拆分

传送门：343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1:

输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

分析：这是一个很经典的问题。可以使用贪心算法。

贪心算法： $2(n-2)>n$ 得到 $n > 4$ ， $3(n-3)>n$ ，得到 $n>4.5$ ，即 $n$ 大于等于 $5$ 的时候。

结论：不能包含 $1$ ，所有的加法因子只能有 $2$ 和 $3$ ，最多只有 $2$ 个 $2$ ，因此加法因子里没有 $4$ 。

贪心选择的证明，可以参考这里：https://leetcode-cn.com/problems/integer-break/solution/tan-xin-xuan-ze-xing-zhi-de-jian-dan-zheng-ming-py/。

Java 代码：

  class Solution2 {
        public int integerBreak(int n) {
            if (n <= 2) {
                return 1;
            }
            if (n == 3) {
                return 2;
            }
            if (n == 4) {
                return 4;
            }
            // 接下来就是 n >= 5 的时候的逻辑了
            int res = 1;
            while (n > 4) {
                res *= 3;
                n -= 3;
            }
            res *= n;
            return res;
        }

        public static void main(String[] args) {
            Solution2 solution2 = new Solution2();
            int integerBreak = solution2.integerBreak(8);
            System.out.println(integerBreak);
        }
    }

C++ 代码：

14-2