题解 | #剪绳子#

- 首先证明递退关系： $a[n] = max(2*a[n-2], 3*a[n-3])$

证明：
1, 已知原始递退关系：

$a[n] = \max_{i=2}^{i<=n-2}(i*a[n-i])$

2, 初始值：

$a[2] = 1$ ;
$a[3] = 2$ ;

3, 当 $i>=4$ 时， $i<=a[i]$

4, 结合 条件1 和 条件3 可知，当 $i>=4$ 时， $i*a[n-i] < a[i]*a[n-i]$ ,

因此

$a[n] = \max_{i=2}^{i<4}(i*a[n-i])$

即

$a[n] = max(2*a[n-2], 3*a[n-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;
    }