题解 | #剪绳子#

- 首先证明递退关系：

 

;
;

3, 当  时，

4, 结合 条件1 和 条件3 可知，当   时， , 

int cutRope(int n) {
        // write code here
        if (n < 3){
            return 1;
        }

        vector<int> square;
        square.push_back(1);
        square.push_back(1);
        square.push_back(1);
        int last = 1;
        for(int i = 3; i <= n; i++) {
            int m2 = square[i-2] * 2;
            int m3 = square[i-3] * 3;
            last = m2 > m3? m2: m3;
            square.push_back(last);
        }
        return last;
    }