14-1.剪绳子
方法一 动态规划
思路：递归式为f(n)=max(f(i), f(n-i))，i=1,2,...,n-1
虽然我现在也没有彻底明白这个递归式是怎么来的，但用的时候还是要注意一下。f(i)是指长度为i时的最大乘积。
但是，上面关于f(i)的定义，当i=1,2,3时是不成立的。
因为，长度为1时，只能返回0；长度为2时，只能返回1,；长度为3时，只能返回2。但是为了方便以后的计算，强行规定f(1)=1,f(2)=2,f(3)=3.
代码
class Solution:
def cuttingRope(self, n: int) -> int:
if n < 2:
return 0
if n == 2:
return 1
if n == 3:
return 2
dp = [0 for _ in range(n+1)]
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
for i in range(4, n+1):
max = 0
for j in range(1, i//2+1):
dP = dp[j]*dp[i-j]
if max < dP:
max = dP
dp[i] = max
return dp[n]
结果
方法二 贪心算法
思路：尽量取3，然后取2.
具体操作如下：对于长度=n的绳子，先取n//3(向下取整)段长度=3m的绳子。如果此时绳子长度仅剩1m，则只取(n//3-1)段3m的绳子(保证剩下的绳长为偶数)。
对于剩下的偶数绳长，将它切成2m一段的绳子即可。
最后的乘积为(3(timesOf2)).
代码
class Solution:
def cuttingRope(self, n: int) -> int:
if n < 2:
return 0
if n == 2:
return 1
if n == 3:
return 2
timesOf3 = n // 3
if n - timesOf3*3 == 1:
timesOf3 -= 1
timesOf2 = (n - timesOf3*3)//2
return pow(3, timesOf3)*pow(2, timesOf2)
结果
写在最后
这道题可以用递归做。但是由于f(1),f(2),f(3)不是当绳子长度为1,2,3时的最大乘积，所以我还没有想到怎么去做。
另外，无论动态规划还是贪心算法，数学原理我仍然蒙圈。这个代码是从剑指offer的C语言翻译过来的，我好像只能做知识的搬运工...