14.【求导+动态规划+贪心】减绳子

题目

给你一根长度为 n 的绳子&＃xff0c;请把绳子剪成整数长度的 m 段&＃xff08;m、n都是整数&＃xff0c;n>1并且m>1&＃xff09;&＃xff0c;每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少&＃xff1f;例如&＃xff0c;当绳子的长度是8时&＃xff0c;我们把它剪成长度分别为2、3、3的三段&＃xff0c;此时得到的最大乘积是18。

分析

&＃xff08;1&＃xff09;数学推导式解决

推论1&＃xff1a;如果把整数n分为两部分&＃xff0c;那么这两部分的值相差越小乘积越大。
举例&＃xff1a;

x*y &＃61; xy; (x-1)*(y&＃43;1)&＃61;xy-(y-x)-1; (x-2)*(y&＃43;1)&＃61;xy-2(y-x)-2;...(x-n)(y&＃43;n)&＃61;xy-n(y-x)-n


推论2&＃xff1a;如果把整数分成n部分&＃xff0c;各个部分相差越小乘积越大。


由于只能拆分为整数&＃xff0c;而e最接近3&＃xff0c;因此尽量拆分为3即可

代码实现

public int cuttingRope(int n) {if (n &＃61;&＃61; 2 || n &＃61;&＃61; 3)return n - 1;int res &＃61; 1;while (n > 4) {//如果n大于4&＃xff0c;我们不停的让他减去3n &＃61; n - 3;//计算每段的乘积res &＃61; res * 3;}return n * res;
}

&＃xff08;2&＃xff09;动态规划

定义一个数组dp&＃xff0c;其中dp[i]表示的是长度为i的绳子能得到的最大乘积。我们先把长度为i的绳子拆成两部分&＃xff0c;一部分是j&＃xff0c;另一部分是i-j&＃xff0c;那么会有下面4种情况&＃xff1a;

• j和i-j都不能再拆了 dp[i]&＃61;j*(i-j);
• j能拆&＃xff0c;i-j不能拆 dp[i]&＃61;dp[j]*(i-j);
• j不能拆&＃xff0c;i-j能拆 dp[i]&＃61;j*dp[i-j];
• j和i-j都能拆 dp[i]&＃61;dp[j]*dp[i-j];

状态转移方程为&＃xff1a;
dp[i] &＃61; max(dp[i], (max(j, dp[j])) * (max(i - j, dp[i - j])));

代码实现

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


&＃xff08;3&＃xff09;贪心

分析 尽量拆分出更多的数3&＃xff0c;注意最后的才出数为1的结果
代码实现

public int cuttingRope(int n) {if(n<4)return n-1;int sum_3 &＃61; n/3;if(n - sum_3*3 &＃61;&＃61;1){sum_3 &＃43;&＃43;;}int sum_2 &＃61; (n-sum_3*3)/2;return (int)Math.pow(3,sum_3)*(int)Math.pow(2,sum_2);}