給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長度的 m 段（m、n都是整數(shù)，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

**狀態(tài)轉(zhuǎn)移： dp[i]=Math.max(Math.max(dp[i-j]j,dp[i]),(i-j)j)
1.剪掉 j長度，剩下的按剩下長度的最優(yōu)
2.剪掉 j長度，剩下的部分不剪
3.不剪

public int cuttingRope(int n) {int[] dp=new int[n+1];dp[1]=1;for(int i=2;i<=n;i++)for(int j=1;j<i;j++)dp[i]=Math.max(Math.max(dp[i-j]*j,dp[i]),(i-j)*j) ;return dp[n];}

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。