剪绳子leetcode343
问题#
给你一根长度为 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。
简单分析#
- 递归，简单粗暴。类似斐波那契数列，可以自顶向下，
F(1) = 1, F(2) = 1, F(3) = 2，显然会超出时间。 - 动态规划，显然递归可以简化，把计算结果累积起来，查表计算。
- 贪心。基于数学分析，当绳子长度大于4时，把剪绳子的段数分为3段的段数越多，则结果越大。长度等于4时，则分为4，因为
2*2>1*3
代码与详细分析#
动态规划#
const cuttingRape = function(n) { const dp = [0, 1]; const M = 1e9+7; for(let i=2; i<=n; i++) { dp[i] = 0; // 初始化i的值，因为上面没有用new Array初始化dp数组的长度 for(let j=1; j<i; j++) { dp[i] = Math.max( dp[i], j*(i-j), j*dp[i-j]) % M; } } return dp[n];}关注点：
- 初始化数组使用的是字面量形式，没有用
new Array(n+1)的形式，因此需要先对dp[i]进行赋值 - 第一层
for循环是求出(0-n)的符合条件的最大值，虽然我们只要第n个值，但是把之前的累积起来，查表用 - 第二层
for循环是遍历，当已知1到n-1的各个状态的值，求长度为n的值。此时可以把n分为j和n-j，上面的i就代表n,j代表从1到i-1可能取的每个值。有两种可能，一种是只剪一次，分成两段j和i-j，那结果就是j*(i-j)，还有一种可能，减了一次长度为j之后再接着对剩下的i-j长度的绳子接着剪，那就直接取之前计算的结果，最大值就是j*dp[i-j].累积，迭代，求出dp[n]
坑#
因为会取模，但是当数值过大时，会损失精度。最后计算的结果有误差。当n=120时就会报错。
数学&贪心#
这个问题可以列一个方程求解。y = Math.pow( (n/x) ) ,计算结果为e，此时可以取到最大值。将每段绳子分成长度为e时候，可以取到最大。由于e=2.78...，而绳子只能取整数，因此可能的取值为2或者3.当n很小时，取2合适，当n较大时，取3合适。这个怎么界定，就是4.当n=4时，(2*2)>1*3，再往后随着n的增大，就是取3合适。
function cuttingRope(n) { const M = 1e9+7; if(n==2 || n==3) { return n-1; } let res = 1; while(n > 4) { n = n - 3; res = (res * 3) % M; } return (res * n) % M;}关注点：
- while内的条件是 (n > 4)，这里就隐含了一些东西，当n小于4时，就直接乘n，等于4时，分成
2*2比分成1*3性价比更高。大于4时，就直接减3，将绳子分成长度为3的一段。
感觉有点渐入佳境？
written bu Rain
20.08.09