問題描述

給你一根長度為n的繩子，請(qǐng)把繩子剪成m段（m、n都是整數(shù)，n>1并且m>1），每段繩子的長度記為k[0],k[1],…,k[m]。請(qǐng)問k[0]xk[1]x…xk[m]可能的最大乘積是多少？

例如，當(dāng)繩子的長度是8時(shí)，我們把它剪成長度分別為2、3、3的三段，此時(shí)得到的最大乘積是18。

輸入描述:
輸入一個(gè)數(shù)n，意義見題面。（2 <= n <= 60）
輸出描述:
輸出答案。

示例1
輸入 8
輸出 18

解題思路

本題有幾個(gè) 可使用動(dòng)態(tài)規(guī)劃算法的明顯特征：
（1）是求最優(yōu)解問題，如最大值，最小值；
（2）該問題能夠分解成若干個(gè)子問題，并且子問題之間有重疊的更小子問題。

通常按照如下 4 個(gè)步驟來 設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法：
（1）刻畫一個(gè)最優(yōu)解的結(jié)構(gòu)特征；
（2）遞歸地定義最優(yōu)解的值；
（3）計(jì)算最優(yōu)解的值，通常采用自底向上的方法；
（4）利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解。

以此題為例，

設(shè)長度為 n 的繩子剪切后的最大乘積為 f(n)，

我們可以將問題看成兩個(gè)子問題，即 f(n) = max(f(j)*f(n-j)) ，j 屬于 (1, 2, …, n/2)

也就是說，我們要求 f(n)，就只要求將 n 分成 n 、n-j 里面的最優(yōu)分解就行了。

為什么 j 的邊界是 n/2 呢？ --> 因?yàn)閷⒁粋€(gè)數(shù)分成兩個(gè)數(shù)，最大的就是 n/2

**假設(shè) n 為 11，**第一刀之后分為了 4-7，而 7 也可能再分成 1-5（7 的最大是 3-4，但過程中還是要比較 1-5 這種情況的），而上一步 4-7 中也需要求長度為 4 的問題的最大值。

可見，各個(gè)子問題之間是有重疊的，所以可以先計(jì)算小問題，存儲(chǔ)下每個(gè)小問題的結(jié)果，逐步往上，求得大問題的最優(yōu)解。

Java 代碼（動(dòng)態(tài)規(guī)劃）

import java.lang.*;public class Solution {public int cutRope(int target) {if (target < 2) {return 0;}if (target == 2) {return 1;}if (target == 3) {return 2;}// ropes[i]表示剪i次時(shí)的最大乘積int[] ropes = new int[target + 1];ropes[1] = 1;ropes[2] = 2;ropes[3] = 3;int temp = 0;for (int i = 4; i <= target; i++) {int max = 0;// f(i) = max(f(j)*f(n-j)), j屬于(1,2,...,n/2)for (int j = 1; j <= i / 2; j++) {temp = ropes[j] * ropes[i - j];max = Math.max(temp, max);}ropes[i] = max;}return ropes[target];} }

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n^2)。
• 空間復(fù)雜度：O(n)。

Java 代碼（貪婪算法）

另解（使用貪婪算法）：

當(dāng) n<5 時(shí)，與動(dòng)態(tài)規(guī)劃的處理一致；

當(dāng)n>=5時(shí)，盡可能多地剪長度為 3 的繩子，當(dāng)剩下的繩子長度為 4 時(shí)，剪成 2-2；

例如：長度為 10 的繩子， 剪成 3-3-2-2

public int maxProductAfterCutting(int length) {if (length < 2) {return 0;}if (length == 2) {return 1;}if (length == 3) {return 2;}// 盡可能多地剪去長度為3的繩子段int timesOf3 = length / 3;// 當(dāng)繩子最后剩下的長度為4的時(shí)候，不能再剪去長度為3的繩子段// 此時(shí)更好的方法是把繩子剪成長度為2的兩段，因?yàn)?x2>3x1if (length - timesOf3 * 3 == 1) {timesOf3 -= 1;}int timesOf2 = (length - timesOf3 * 3) / 2;return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2)); }

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(1)。
• 空間復(fù)雜度：O(1)。

雖然貪婪算法的時(shí)間復(fù)雜度低，但面試官一般都會(huì)要求證明

數(shù)學(xué)證明：

https://www.jianshu.com/p/0a13e48aa4af

總結(jié)

以上是生活随笔為你收集整理的剑指Offer：剪绳子(动态规划、贪婪算法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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