LeetCode： 剑指 Offer 14- II. 剪绳子 II
题意与 剪绳子Ⅰ 一样， 不同是把 n 的范围由 58 提升到了 1000
解法相同
1 数论 大于 1 的任意一个数，都可以拆分位为2、3组成。 6 >> 2 2 2 >> 222 = 8 6 >> 3 3 >> 3*3 = 9 拆的 3 越多，乘积越大。
2 dp 写法。由于dp 需要 max 比较取得较大的一个作为状态保存，所以比较的中间量不能直接 mod 1000000007 缩小数据， 否则会改变结果。 这里 dp 利用到了 BigInteger 这个数据类型。
dp[i] 的语义： 长度为 i 的绳子分段后可以取得的最大乘积 j 是 i 拆分出来的整数， 所以 j < i ，另一段 i - j , 如果 i - j 还可以拆分出整数 >> dp[i - j]
数论代码
public int cuttingRope(int n) { if(n <= 3) return n - 1; int div = n / 3; int rem = n % 3; long ans = 1; int mod = 1000000007; for (int i = 0; i < div - 1; i++) { ans = (ans * 3) % mod; } // 还剩最后一段 div - 1 if(rem == 2){ ans *= (rem * 3); // 多出的 2 单独作为一段乘积更大 }else { // rem == 0 || 1 ans *= (rem + 3); // 多出的是0 / 1 与最后一段 3 拼在一起乘积更大 } return (int) (ans % mod); }dp 代码 转移方程： dp[i] = Math.max(Math.max(j * (i - j), j * dp[i - j]), dp[i])
import java.math.BigInteger; class Solution { public int cuttingRope(int n) { BigInteger[] dp = new BigInteger[n + 2]; int mod = 1000000007; // n > 1 dp[0] = new BigInteger("0"); dp[1] = new BigInteger("0"); dp[2] = new BigInteger("1"); dp[3] = new BigInteger("2"); for (int i = 2; i < n + 2; i++) { dp[i] = new BigInteger("0"); for (int j = 1; j < i; j++) { BigInteger temp = dp[i - j].multiply(new BigInteger(j + "")).max(new BigInteger((j * (i - j)) + "")); dp[i] = dp[i].max(temp); // dp[i] = Math.max(Math.max(j*(i - j), j*dp[i - j]), dp[i]); } } return dp[n].mod(new BigInteger(mod + "")).intValue(); } }Java dp
大佬技巧
