剑指 Offer 14- I. 剪绳子

剑指 Offer 14- I. 剪绳子

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

思路

golang

1.采用动态规划的思想：

• 因为所给条件n>1,且m>1。所以初始dp[2]=1（切成两段，即m=2。此时乘积为1x1=1）dp[i]表示长度为i的绳子的最大乘积

• 对于长度为i的绳子来说，先切了一段j，则剩下长度为(i-j)可以切也可以不切

  • 如果切，乘积为j*dp[i-j]
  • 如果不切，乘积为j*(i-j)

  则状态转移方程为：max(j*dp[i-j],j*(i-j))，从1<=j<i遍历

• 返回值为长度为n的绳子剪成m段的最大乘积，即dp[n]

时间复杂度：对于从2到n的每一个数都要计算dp值，计算一个dp的值需要O(n)时间，故总体的时间复杂度为O(n²)

空间复杂度：构建一个dp数组，则空间复杂度为O(n)

func cuttingRope(n int) int {
    dp := make([]int,n+1)
    dp[2] =1 //初始值
    for i:=3;i<n+1;i++{
        for j:=2;j<i;j++{
            dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j])) //原来的最大乘积和现有的乘积进行比较 取最大值
        }
    }
    return dp[n]
}

func max(x,y int) int{
    if x > y{
        return x
    }
    return y
}

2.采用数学推导的方式：
可以证得当每段的长度为整数3时，所得到乘积最大，因此尽可能的将长度为n(n>3)的绳子以长度3切割成m份。最后一段绳子的长度可能如下：0，1，2
当剩余长度为0时，直接返回pow(3,m)
当剩余长度为1时，需要将倒数第二段与1合并分成两段长度为2的，因为2x2>3x1，返回pow(3,m-1)*4
当剩余长度为2时，保留最后一段不切割，因为2>1x1，返回pow(3,m)*2

下面证明为什么长度为整数3时，所得乘积最大：

由均值不等式：算数平均数>=几何平均数可知

\[\frac{n1+n2+...+na}{a}\geq\sqrt[a]{n1n2...na} \]

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

• 将绳子按长度x等分为a段，即n=ax，则乘积为x^a。观察以下公式，由于n为常数，故当x^1/x取得最大值时，整体乘积最大。

  \[x^a=x^\frac{n}{x}=(x^\frac{1}{x})^n \]

• 可将问题转化为求y= x^1/x的极大值，因此对x求导数

  \[\ln{y} = \frac{1}{x}\ln{x} \quad两边同时取对数 \]
  \[\frac{1}{y}\ln{y}=\frac{1}{x^2}-\frac{1}{x^2}\ln{x}\quad 对x求导 \]
  \[y=\frac{1-\ln{x}}{x^2}x^\frac{1}{x}\quad整理得 \]

• 令 y=0 ，则 1 - ln x = 0，易得驻点为 x₀=e≈2.7，且为极大值点。由于切分长度必须为整数，故接近e得整数为2或3，带入原方程可得：当长度为3时，乘积达到最大

  \[y(3)=(3)^\frac{1}{3}\approx1.44 \]
  \[y(2)=(3)^\frac{1}{2}\approx1.41 \]

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

时间复杂度：O(1)

空间复杂度：O(1)

func cuttingRope(n int) int{
    if n<=3{
        return n-1
    }

    a,b := n / 3,n%3
    if b == 0{
        return int(math.Pow(3,float64(a)))
    }
    if b == 1{
        return int(math.Pow(3,float64(a-1))) * 4
    }
    return int(math.Pow(3,float64(a)))*2
}

js

/**
 * @param {number} n
 * @return {number}
 */
//1.动态规划
// var cuttingRope = function(n) {
//     let dp = new Array(n+1).fill(0);
//     dp[2] = 1;
//     for(let i=3;i<n+1;i++){
//         for(let j=2;j<i;j++){
//             dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
//         }
//     }
//     return dp[n];
// };

//2.数学推导
var cuttingRope = function(n) {
    if(n<=3) return n-1;
    let a=Math.floor(n/3),b=n%3;
    if(b==0) return Math.pow(3,a)
    if(b==1) return Math.pow(3,a-1)*4
    return Math.pow(3,a)*2
}

剑指 Offer 14- I. 剪绳子

原文：https://www.cnblogs.com/zmk-c/p/14640446.html