剪绳子
题目描述：
解题思路：
思路一：贪心策略：
代码如下所示：
class Solution {
public:
int cuttingRope(int n
)
{
if (n
< 4)
return n
- 1;
int a
= n
/ 3, b
= n
% 3;
if (b
== 0)
return a
= pow(3, a
);
if (b
== 1)
return a
= pow(3, a
-1) * 4;
if (b
== 2)
return a
= pow(3, a
) * 2;
return a
;
}
};
思路二：
主要的理念还是尽量的去减长度为3的绳子，这样可以让最后的结果尽可能的大3(n-3)>2(n-2)
class Solution {
public:
int cutRope(int number
)
{
if(number
==2||number
==1)
return 1;
if(number
==3)
return 2;
int sum
=1;
while(number
>4)
{
sum
*=3;
number
-=3;
}
return sum
*number
;
}
};
思路三：动态规划
class Solution {
public:
int cutRope(int number
) {
vector
<int>dp(number
+1,1);
for(int i
=1;i
<=number
;i
++){
for(int j
=1;j
<=i
;j
++){
dp
[i
]=max(dp
[i
],dp
[i
-j
]*j
);
}
}
return dp
[number
];
}
};
测试用例：
功能测试：绳子的初始长度大于5边界值测试：绳子的长度分别为0，1，2，3，4
