题解 | #剪绳子#
剪绳子
https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8
- 首先证明递退关系：)
证明：
1, 已知原始递退关系：
1, 已知原始递退关系：
2, 初始值：
3, 当 
时， ![i<=a[i]](https://www.nowcoder.com/equation?tex=i%3C%3Da%5Bi%5D)
4, 结合 条件1 和 条件3 可知，当 时， ![i*a[n-i] < a[i]*a[n-i]](https://www.nowcoder.com/equation?tex=i*a%5Bn-i%5D%20%3C%20a%5Bi%5D*a%5Bn-i%5D)
,
因此
即
- 代码实现
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;
}
