动态规划
https://leetcode-cn.com/problems/integer-break/solution/dong-tai-gui-hua-zhi-xing-yong-shi-da-bai-100-c-by/
动态规划
class Solution {
public:
int cuttingRope(int n) {
vector<int> dp(n+1,1);
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++)
dp[i]=max(dp[i],max(dp[j],j)*(i-j));
}
return dp[n];
}
};
贪心
整数拆分 (贪心,清晰图表解析)
class Solution {
public:
int cuttingRope(int n) {
if(n<4) return n-1;
int a=n/3,b=n%3;
if(b==0) return pow(3,a);
if(b==1) return pow(3,a-1)*4;
return pow(3,a)*2;
}
};
面试题14- II. 剪绳子 II(贪心 + 快速幂求余,清晰图解)
class Solution {
public:
int cuttingRope(int n) {
if(n<4) return n-1;
int b=n%3,p=1000000007;
long rem=1,x=3;
for(int a=n/3-1;a>0;a/=2){
if(a % 2) rem=(rem*x)%p;
x=(x*x)%p;
}
if(b==0) return int(rem*3%p);
if(b==1) return int(rem*4%p);
return int(rem*6%p);
}
};