LeetCode 343. Integer Break

Problem

剑指 Offer 14- I. 剪绳子 I
LeetCode 343. Integer Break

1. 题目简述

给出一个正整数数字n。将其分割为至少两个正整数，使其加和为n。要求分割后的数字乘积最大。返回乘积。

Example 1:

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

2 <= n <= 58

2. 算法思路

动态规划

dp[n]表示对于组正整数n，其切分后的最大乘积。我们可以得到递推式：

for j in range [1, n/2]:
    dp[n] = max(dp[n], max(j, dp[j]) * max(n - j, dp[n - j]));

其含义为我们依次取可能的最后一段切分j，那么最大值就等于前后两段分别的最大值乘积。

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]));
            }
        }

        return dp[n];
    }
}

数学方法（贪心法）

证明参考: Krahets的题解

通过数学证明，我们可以算出，如果想找最大值，当长度大于4时，每次至以3为大小进行切分，直到长度小于等于4，然后相乘。这道题的进阶版是需要对结果取模。这里要用到取余的性质，同见数学证明，以下的解法是包含了取余，对应题目: 剑指 Offer 14- II. 剪绳子 II

class Solution {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }

        long res = 1;
        while (n > 4) {
            n -= 3;
            res = 3 * res;
            res = res  % 1000000007;
        } 

        return (int)(res * n % 1000000007);
    }
}