【17贪心算法】剪绳子

这题和我之前做的https://www.cnblogs.com/Jun10ng/p/12363679.html

是同一个题目，但是现在多了一个条件 1<=n<=1000

如果还是用dp的话，dp数组就要用大数类BigInteger

但是，还有一种解法，贪心算法

题目

同上

思路

原本打算用大数类的dp数组

但是看了下贪心的解法，也很容易理解

就是一直乘3，

收获

大数类的使用

头文件是 java.math.BigInteger

初始化函数是BigInteger（String类的数字）

代码（贪心）

class Solution {
public int cuttingRope(int n) {
if(n == 2) {
return 1;
}
if(n == 3){
return 2;
}
int mod = (int)1e9 + 7;
long res = 1;
while(n > 4) {
res *= 3;
res %= mod;
n -= 3;
}
return (int)(res * n % mod);
}
}