剑指Offer——剪绳子（JS实现）

题目描述

解题思路

• 这道题在JS题解中一般给出了两种解法，一是动态规划，二是贪心算法
• 本次采用的是动态规划，主要是想强化自己在这方面的学习
• 贪心的思想是构造3，尽可能多的3相乘会使得乘积最大，通过对3取余的三种情况来分别推导最后的乘积
• 动态规划的思想则是首先构造一个长度为n+1的全1数组，这里的n代表的是绳子的总长度，之所以要进行+1，是因为我们操作的始终是数组的下标，dp[i]代表什么含义，是我们必须要好好理解的，dp[i]代表的是长度为i的绳子被剪成n段后的最大乘积
• 动态规划的结束条件是dp[2]=1,因为2米的绳子可以拆成1+1，最后的乘积是1
• 动态规划的一般方程是dp[i] = Max(dp[i],j * (i-j),j * dp[i-j])
• 理解上面的一般方程是解题关键，dp[i]则是不断给修改的长度为i的绳子被剪成n段后的最大乘积，这里的i是从3开始遍历的，j则是从1开始遍历的，i-j代表的是如果一段绳子被拆成两段，另一段的长度，但是j * (i-j)只是判断了一段绳子被剪成两段后的所有结果，但是有时候最大乘积是3个或者更多数字的乘积，比如绳子的长度是8，则可以拆成3 * 3 * 2 = 18，所以动态规划的第三个方程就很关键了，j是从1开始遍历的，此时第1个i-j就是7，所以i 和 i-j的和始终是8，当i=2,i-j等于6的时候就会出现 2 * 3 * 3就是我们要求的最大乘积，通过j * dp[i-j]会无形中引入更短的数字乘积，而不只是两两相乘。

为了帮助理解，我制作了，下面的一张图，以dp[4]为例，看懂本题的动态规划

解题代码

var cuttingRope = function(n) {
    // 本题可以采用动态规划的思想
    // 动态规划的结束条件是dp[2] = 1  代表的含义是长度为2的绳子剪成几段后最大乘积是1
    const dp = new Array(n + 1);
    dp.fill(1);
    for (let i = 3; i < dp.length;i++) {
        for (let j = 1; j < i;j++) {
            dp[i] = Math.max(dp[i],j*(i-j),j*dp[i-j])
        }
    }
    return dp[n]
};

总结（本题给我们的启示思路）

• 启示一：学会使动态规划
• 启示二：学会如何遍历值为x的两个元素