题解 | #剪绳子#

```function cutRope(number)
{
    // write code here 这是一道很经典的题
    //一.动态规划（递归）：对于长度为n的绳子，剪第一刀时，有n-1种方式，剪出来的绳子长度可能从1到n-1
    //因此fn=fi*fn-1 0<i<n 选出不同i的最大乘积 对于剩下的绳子可以自上往下递归求解
    //但是以上太多重复子问题，另一种思路是从下往上，易得f2=1 f3=2。f4时，就是4了，可以切成2和2。
    if(number<2){return 0}
    if(number===2){return 1}
    if(number===3){return 2}
    //以上时父段绳子长度小于等于3的返回值，因为题目要求必须切一刀。而子段绳子为2或者3时没有切的必要，注意区分。
    let resArr=[0,1,2,3] //存储绳子某个长度的最大乘积值。因为对于子段绳子长度小于等于3时，没有切的必要，所以等于自身。
    //其实想明白这里可以用贪婪算法，具体参考其他解法
    for(let i=4;i<=number;i++){ //i++，表明自下而上
        let arr=[]
        for(let j=1;j<=i/2;j++){
           let temp =resArr[j]*resArr[i-j]
           arr.push(temp) //用数组记录对于长度i子段绳子不同切法的乘积值
        }
        let tempMax=Math.max(...arr) //得出对于i长度子段绳子的最大乘积值
        resArr[i]=tempMax //记录，给i增大后的递归作铺垫
    }
    return resArr[number]
}
module.exports = {
    cutRope : cutRope
};