剑指 Offer 14- I. 剪绳子image.png

（1）DFS超时

  1. class Solution:
  2.     def cuttingRope(self, n: int) -> int:
  3.         def dfs(chengji,changdu):
  4.             if changdu==n:
  5.                 ans.append(chengji)
  6.             if changdu<n:
  7.                 for j in range(1,n):
  8.                     dfs(chengji*j,changdu+j)
  9.         ans=[]
  10.         dfs(1,0)
  11.         # print(ans)
  12.         return max(ans)

（2）动态规划

image.png

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

×（3）贪心