【剑指offer】剪绳子（两种思路）

class Solution {
public:
    int cutRope(int number) {
        if(number == 2) return 1;
        if(number == 3) return 2;
       //动态规划, O(n)
        vector<int> res = {0, 1, 2, 3};//数组这里记录的长度是不考虑继续再剪的最长长度，和前面的返回值稍有区别。
        for(int i = 4; i <= number; i++){
            int j = i / 2;
            res.push_back(res[j] * res[i - j]);
        }
        return res[number];
        /*
        找到规律发现，最大乘绩的分法一般就是一堆3和一个2或者两个2的组合
        O(logn)
        int x = number % 3;
        int y = number / 3;
        if(x == 0)
            return (long long) pow(3, y);
        else if(x == 1)
            return 2 * 2 (long long) pow(3, y - 1);
        else
            return 2 * (long long) pow(3, y);
        */
    }
};