Joyce' Blog
0%

剪绳子

发表于 更新于

题目描述

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

2 <= n <= 58

链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

题解

总觉得像道数学题……动态规划求解。

初始状态：dp[2]=1，dp[i]在前面的基础上（dp[j], j=2,…,i-1）选择剪(dp[j]*(i-j))或不剪((i-j)*j)

dp[i]=max((i-j)*j, dp[j]*(i-j), j=2,…,i-1)

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

题目描述

和上面一样，只不过2 <= n <= 1000，答案需要取模 1e9+7（1000000007）

题解

或者，就直接用别人推导出的公式吧……切分规则：

  • 最优： 3 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2三种情况。
  • 次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
  • 最差： 1 。若最后一段绳子长度为 1 ；则应把一份 3 + 1 替换为 2 + 2，因为 2*2 > 3*1。

链接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/

但是会遇到溢出的问题……改用long long int的话就可以。

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
28
29
30
31
int cuttingRope(int n) {
    if(n<4)return n-1;
    int count=n/3;
    int left=n%3;
    long long int res=1;
    if(left==1)
    {
        count--;
        for(int i=0;i<count;i++)
        {
            res=(res*3)%1000000007;
        }
        res=(res*4)%1000000007;
    }
    else if(left==2)
    {
        for(int i=0;i<count;i++)
        {
            res=(res*3)%1000000007;
        }
        res=(res*2)%1000000007;
    }
    else
    {
        for(int i=0;i<count;i++)
        {
            res=(res*3)%1000000007;
        }
    }
    return res;
}