《剑指offer》 14.剪绳子

剑指offer
留言

note:

动态规划有四个特点

  1. 求最优解
  2. 整体问题的最优解依赖于各个子问题的最优解
  3. 大问题可以分解为若干个小问题，这些小问题之间还存在重叠的更小的子问题
  4. 从上往下分析问题，从下往上求解问题

——摘自《剑指offer》

题目描述

给你一根长度为 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：

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

示例 2:

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

提示：

  • 2 <= n <= 58

方法一 动态规划

思路

分析问题，剪绳子问题，只给出了绳子的总长度，没有给要剪成几段，只是要求整数长度，以及剪完之后的所有子绳子的长度乘积最大。

分析每次剪绳子，假设我要减的绳子长度为$n$，我剪了$i$，则剩余$n-i$长度，那么他们的乘积为$i(n-i)$，此题目要求乘积最大，就是$i(n-i)$最大。但是问题是$i,j$同样是不定的，他们也要再被剪，剪的规则同样是上述的规则，所以很容易得出递推公式如下：

显然这个递推公式如果直接用递归等做法就会有大量重复计算，所以我们可以使用动态规划的求法，反向进行求解并记录子问题的结果。

  • 状态转移方程：
  • 初始状态：分析以下我们的动态规划过程，我们为了求乘积，默认了一件事，就是长度为$i$的绳子至少分为两段。也就是说我们不考虑子绳子的长度为0——也就是不剪的情况。但是事实上我们很容易发现，在$n<=3$时，不剪的情况反而是乘积最大的情况(具体推导是基本不等式)——事实上问题就在于，一刀不剪不代表产生了一个长度为0的子绳子和一个长度为i的子绳子，而是仅仅只有一个子绳子，乘积应该为绳长本身。那么根据上述分析，我们可以需要总结出4个初始状态，分别是
    • dp[0] = 0;
    • dp[1] = 1;
    • dp[2] = 2;
    • dp[3] = 3;
  • 返回值dp[n]。

通过上文的分析，我们会发现，本质上我们的状态转移方程还存在问题，实际上是利用了长度大于等于4的绳子的子绳子乘积比绳子本身要大这一推断，但是状态转移方程直接没有考虑可能存在的绳子本身的长度大于任何子绳子乘积的这一情况，也就是状态转移方程默认绳子必须要剪。所以我们需要4个初始状态，来完善我们的动态规划，（这也是《剑指offer》一书中提供的解法）。但实际上我们题目中有条件$m>1$，也就是说第一次一定要剪，那么我们其实是需要对$n<4$的情况做一个特殊处理的，这个特殊处理是

1
2
3
4
5
6
if(n<2)
	return 0;
if(n==2)
	return 1;
if(n==3)
	return 2;

代码

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
class Solution {
public:
    int cuttingRope(int n) {
        if(n<2)
            return 0;
        if(n==2)
            return 1;
        if(n==3)
            return 2;

        vector<int> dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        
        int temp=0;
        for(int i=4;i<=n;i++){
            temp=0;
            for(int j=1;j<=i/2;j++){		// 小技巧，j无需遍历[1,i)，因为剩下的和剪去的是镜像对称的。
                temp = max(temp,dp[j]*dp[i-j]);
                dp[i] = temp;
            }
        }
        return dp[n];
    }
};

复杂度分析

  • 时间复杂度$O(n^2)$。从4到n的每一个整数都要计算对应的dp值，计算一个整数对应的dp值需要的是$O(n)$的时间复杂度，所以总时间为$O(n^2)$
  • 空间复杂度$O(n)$。其中，n是给定的正整数。创建一个数组dp，长度为n+1

方法二 另一种动态规划

思路

我们还有一种状态转移方程的写法可以不需要这么多初始状态与特殊处理。

  • 状态转移方程：

    这个状态转移方程应该这样理解：对于长度为n的绳子，我们尝试先剪出来一段，这一段的距离在$[1,n)$区间内，也就是说第一段一定要剪（不然无法进行乘法运算，左闭右开也是因为剪剩下的不能为0，这符合题目中$m>1$的要求）。然后剩下的部分，我们要进行讨论分析——是一刀不剪，还是用它剪开之后的乘积，两者取其大。然后我们在所有剪出来一段的情况中，进行选择最大的，作为dp[i]的值

  • 初始状态：

    • dp[0] = 0
    • dp[1] = 0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n+1);
        
        for(int i=2;i<=n;i++){
            int curMax=0;
            for(int j=1;j<i;j++){
                curMax = max(curMax,max(j*(i-j),j*dp[i-j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
};

复杂度分析

  • 时间复杂度$O(n^2)$。从2到n的每一个整数都要计算对应的dp值，计算一个整数对应的dp值需要的是$O(n)$的时间复杂度，所以总时间为$O(n^2)$
  • 空间复杂度$O(n)$。其中，n是给定的正整数。创建一个数组dp，长度为n+1

方法三：贪心思想

思路

贪心的重点在于怎么贪以及如何证明贪心是合理的。

  • 本题的贪心策略：

当n>=5时，尽可能多的剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子

  • 策略正确性的说明：
    • 当n>=5时，可以证明$2(n-2)>n$并且$3(n-3)>n$。即绳子剩下的长度大于或者等于5的时候，我们把它剪成长度为3或为2的绳子段。
    • 另外当n>=5时，3(n-2)>=2(n-2)，所以我们应该尽可能地多剪长度为3的绳子段
    • 当n==4时，可以发现最大的剪法是2*2=4

该策略的证明略，可见题解中的数学推导

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return n-1;
        int a = n/3, b = n%3;

        if(b==1)    return pow(3,a-1)*4;
        if(b==2)    return pow(3,a)*2;
        return pow(3,a);
    }
};

复杂度分析

  • 时间复杂度$O(1)$
  • 空间复杂度$O(1)$

剑指 Offer 14- II. 剪绳子 II

题目描述

给你一根长度为 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。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

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

示例 2:

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

提示：

  • 2 <= n <= 1000

思路

整体思路和上面的剪绳子I完全相同，但是由于$2<=n<=1000$,显然会发生溢出在进行乘方运算时。所以无法使用函数库中的pow函数，需要我们自己设计求幂运算，在运算过程中进行求余运算。大致有两种方法

  • 循环求余
  • 快速幂求余

循环求余利用的公式是：

快速幂求余利用的公式是：

他们的时间复杂度分别为$O(n)$和$O(logN)$

代码

循环求余：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return n-1;
        // 分析拆3之后最后剩下啥
        int a = n%3;
        // 幂结果ans，初始幂底为3
        long long ans=1, c=3;
        int b = n/3-1;
        // 循环求余过程
        while(b){
            ans = (ans*c)%1000000007;
            b--;
        }
        if(a==0) return (int)(ans*3%1000000007);
        if(a==1) return (int)(ans*4%1000000007);
        else return (int)(ans*6%1000000007);
    }
};

快速幂求余

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return n-1;
        // 分析拆3之后最后剩下啥
        int a = n%3;
        // 快速幂结果ans，初始幂底为3
        long long ans=1, c=3;
        // 快速幂过程，从n/3-1开始是因为
        for(int b=n/3-1;b>0;b=b/2){
            if(b%2==1) ans = (ans*c)%1000000007;
            c = (c*c)%1000000007;
        }
        if(a==0) return (int)(ans*3%1000000007);
        if(a==1) return (int)(ans*4%1000000007);
        else return (int)(ans*6%1000000007);
    }
};

复杂度分析

  • 时间复杂度
    • 循环求余的时间复杂度为$O(N)$
    • 快速幂求余的时间复杂度为$O(logN)$
  • 空间复杂度$O(1)$