劍指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的兩個元素