C++ 动态规划与贪心，两种解法

1.贪心
贪心选择为3 (经过数学推理证明)
时间复杂度：O(1)
空间复杂度：O(1)

class Solution {
public:
    int cutRope(int number) 
    {
        if(number <= 3)    return number-1;
        int cnt = number/3;

        if(number%3 == 0)    return pow(3, cnt);
        else if(number%3 == 1)    return pow(3, cnt-1)*4;
        else    return pow(3, cnt)*2;
    }
};

2.动态规划
时间复杂度：O(N2)
空间复杂度：O(N)

​class Solution {
public:
    int cuttingRope(int n) 
    {
        if(n == 2) return 1;
        if(n == 3) return 2;

        int* dp = new int[n+1];
        dp[2] = 2;
        dp[3] = 3;

        int maxCut;
        for(int i=4; i<=n; ++i)
        {
            maxCut = 0;
            for(int j=2; j<=i/2; ++j)
            {
                maxCut = max(maxCut, dp[i-j]*dp[j]);
                dp[i] = maxCut;
            }
        }
        return dp[n];
    }
};