給你一根長度為 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

步驟一、確定狀態:

確定dp數組及初始化含義 dp[i]:長度為i的繩子剪成m段得到的最大乘積

步驟二、推斷狀態方程:

1. j×(i?j)
2. 從當前j這里獲得的最大乘積為:max(j×(i?j),j×dp[i?j]) 而當前i處獲得的最大乘積: dp[i]=max(max(j×(i?j),j×dp[i?j]),dp[i])

步驟三、規定初始條件:

初始條件:
dp[0], d[1]是沒法分解的，所以從dp[2]開始，初始化為1即可

步驟四、計算順序:

這個題目需要兩層遍歷了，因為當前i的dp值，需要依賴于前面的所有dp值。 i從3到n遍歷

j從2到i?1遍歷

class Solution:def cuttingRope(self, n: int) -> int:dp = [0] * (n + 1)dp[2] = 1for i in range(3, n+1):for j in range(2, i):dp[i] = max(max(j*(i-j), j*dp[i-j]), dp[i])return dp[n]

總結

以上是生活随笔為你收集整理的88. Leetcode 剑指 Offer 14- I. 剪绳子 (动态规划-基础题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。