每天一道leetcode(Day 67)

剑指 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

解题思路

本题思路：动态规划

本题想要求长度为 n 的绳子，所以先得出状态转移方程；这里我们用数组 dp[n]来表示长度为 n 的绳子截取后的最大乘积；

1. 初始化数组 dp[n]，数组下标为i(1<i<=m)，由于当 i 为 2 时，我们已经知道值为 1，所以 dp[2]=1;
2. 当 i>2 时，讨论截取绳子的情况，假设当前截取的长度为 j，

• 若 j=1，则 dp[i] = 1 * dp[i-1]，此时dp[i]在dp[i-1]的基础上没有任何增加，因此不用考虑j=1的情况；
• 由上步可知j的取值范围为[2,i)，当j>=2,时，截取了j的长度之后，绳子剩余的长度为i-j，此时剩余的长度可以选择继续截取或者是不截取，若继续截取则dp[i]=j*dp[i-j]；若不截取，则绳子只有两段，此时dp[i] = j*(i-j)；最终 dp[i]的值则是在 j 的循环中取得最大值即可：dp[i] = Math.max(dp[i],j*(i-j),j*dp[i-j])(2=<j<i);
• 根据上一步循环，结束之后返回dp[n]即可；

代码

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
  const 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], j * (i - j), j * dp[i - j]);
    }
  }
  return dp[n];
};

参考

剑指 Offer 14- I. 剪绳子