剪绳子问题是一个经典的动态规划问题，其描述为：给定一根长度为 n 的绳子，要求将其剪成 m 段（m > 1，整数），并且使得这些段的长度乘积最大化。可以将这个问题描述为一个最优化问题，即找到最大的乘积。
动态规划 剪绳子问题
2、动态规划简介
无处不在的规划
动态规划是一种常见的解决最优化问题的方法，其基本思路是将问题分解为若干子问题，通过解决子问题来解决原始问题，同时利用子问题的解来构建原始问题的解。
3、解题思路定义状态：设 f(n) 为长度为 n 的绳子剪成若干段后的最大乘积。
状态转移方程：对于长度为 n 的绳子，可以考虑将其剪成两段，分别是长度为 i 和 n-i。剪成两段后，可以选择继续剪或者不剪。如果不剪，则长度为 n 的绳子剪成两段后的最大乘积就是 i 和 n-i 的乘积。如果剪，则长度为 n 的绳子剪成两段后的最大乘积就是 i 和 f(n-i) 的乘积。因此，状态转移方程可以表示为：
f(n) = max(i * (n - i), i * f(n - i))边界条件：长度为 2 的绳子只能剪成两段长度为 1 的绳子，因此 f(2) = 1。
自底向上求解：根据状态转移方程和边界条件，可以使用动态规划自底向上地求解 f(n)，从小到大逐步计算出长度为 2、3、4、...、n 的绳子剪成若干段后的最大乘积。
回归数学本质
返回结果：最终返回 f(n) 即可。
4、python解决方案def maxProductAfterCutting(length): if length < 2: return 0 if length == 2: return 1 if length == 3: return 2 # 创建一个列表用于保存各个长度的最大乘积 products = [0] * (length + 1) products[1] = 1 products[2] = 2 products[3] = 3 # 自底向上求解 for i in range(4, length + 1): max_product = 0 for j in range(1, (i // 2) + 1): product = products[j] * products[i - j] if product > max_product: max_product = product products[i] = max_product return products[length]# 测试print(maxProductAfterCutting(8)) # 输出18，剪成长度分别为2、3、3的三段，乘积最大为18这段代码中，maxProductAfterCutting 函数接受一个整数 length，表示绳子的长度，然后返回将长度为 length 的绳子剪成若干段后的最大乘积。
4、java解决方案package DynamicPrograming;import utils.LeeCodeUtils;public 剪绳子 { static int getResult(int n){ if(n < 2) return 0; if(n == 2) return 1; //1*1 if(n == 3) return 2; //1*2 int time3 = n/3; if(n-3*time3 == 1) time3--; int time2 = (n-3*time3)/2; return (int) (Math.pow(3,time3)*Math.pow(2,time2)); } static int integerBreak(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(dp[i], Math.max(j*(i-j), dp[j]*(i-j))); } } LeeCodeUtils.displayArrayinOneLine(dp); return dp[n]; } static int getLast(int n){ if(n < 2) return 0; if(n == 2) return 1; //1*1 if(n == 3) return 2; //1*2 // n >= 4的case int[] d = new int[n+1]; d[1] = 1; d[2] = 2; d[3] = 3; for(int i = 4;i<=n;i++){ d[i] = Math.max(d[i - 2] * 2, d[i - 3] * 3); } LeeCodeUtils.displayArrayinOneLine(d); return d[n]; } public static void main(String[] args) { int n = 18; System.out.println(getResult(n)); System.out.println("-----------------------"); System.out.println(integerBreak(n)); System.out.println("***********************"); System.out.println(getLast(n)); }}未完待续，喜欢的点个关注 谢谢。
创作不易 点个关注 谢谢
