Pengjielee's blog

题目

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0] x k[1] x … x k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

输入描述: 输入一个数n，意义见题面。（2 <= n <= 60）
输出描述: 输出答案。

示例1  
输入  
8  

输出  
18

详解

动态规划（自底向上）

使用动态规划，从已知值 F(2) 逐步迭代到目标值 F(n)，它是一种自底向上的方法。

算法:

建立一维动态数组 dp；
边界条件：dp[1] = dp[2] = 1，表示长度为 2 的绳子最大乘积为 1；
状态转移方程：dp[i] = max(dp[i], max((i - j) * j, j * dp[i - j]))，可以这样理解：

dp[i] = max(【dp[i]】, max(【(i - j) * j】, 【j * dp[i - j]】))       
【】0，维护原状态，不剪；
【】1，从j处剪一下，剪下来的部分是i-j，i-j不再剪了；
【】2，从j处剪一下，剪下来的部分是i-j，i-j继续剪；

JS实现

确定边界条件和状态转移方程：
当绳子长度n为1时，最大乘积为0；
当绳子长度n为2时，可以剪成（1+1），最大乘积为1；
当绳子长度n为3时，可以剪成（1+2, 1+1+1），最大乘积为2；当绳子长度n为4时，可以剪成（1+1+1+1, 1+2+1, 2+2, 1+3），最大乘积为4；
当绳子长度n为5时，可以剪成（1+1+1+1+1, 1+2+2, 3+2, 1+2+1+1, 1+3+1, 1+4），最大乘积为6；
我们可以看到，当绳子长度n大于等于4时，f(n) = max( f(j) * f(n-j) )，其中1 < j <= [n/2]，因此我们可以用遍历来实现状态转移方程。

function cutRope(n) {
  let res = [0, 1, 2, 3];
  if (n < 4) {
    return n - 1;
  }
  if (res[n]) {
    return res[n];
  }

  for (let i = 4; i <= n; i++) {
    let max = 0;
    for (let j = 1; j <= i / 2; j++) {
      let cur = res[i - j] * res[j];
      max = max < cur ? cur : max;
    }
    res[i] = max;
  }
  return res[n];
}

剪绳子(JS实现)
https://blog.csdn.net/qq_36330972/article/details/103493083
https://blog.csdn.net/qq_40816360/article/details/95032134
https://blog.csdn.net/zjw_python/article/details/82730276

67.剪绳子.md

题目

详解

JS实现

More