剑指offer--14-II 剪绳子
题目
代码
和剪绳子I不同的是，此题涉及到大数运算，要么用BigInteger类要么如下代码所示根据数学原理尽可能接近3输出。
class Solution {
public int cuttingRope(int n) {
if(n < 4) return n - 1;
long res = 1;
while(n > 4){
res = res * 3 % 1000000007;
n -= 3;
}return (int) (res * n % 1000000007);
}
}
import java.math.BigInteger;
class Solution {
public int cuttingRope(int n) {
BigInteger[] dp = new BigInteger[n + 1];
Arrays.fill(dp, BigInteger.valueOf(1));
for(int i = 2; i < n + 1; i++){
for(int j = 1; j < i; j++){
dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));
}
}
return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
}
}
