剑指offer14:剪绳子

第一题：

动态规划思路：
写出状态转移方程，设f(n)表示长度为n的绳子剪出的最大乘积值
f(n)=max{f(i)*f(n-1)}，i的区间在[1,n/2]，这样就很容易写出代码：
class Solution {
public:
int cuttingRope(int n) {
if(n==2) return 1;
if(n==3) return 2;
vector ans(n+1);
ans[1]=1;
ans[2]=2;
ans[3]=3;
for(int i=4;i<=n;++i) { int maxVal=0; for(int j=1;j<=i/2;++j) { maxVal=max(maxVal,ans[j]*ans[i-j]); }

剑指offer14:剪绳子最先出现在Python成神之路。