Java思路:
1. 重点:能用3绝不用2
2. 如果是3的倍数的话,就划分成几个3相乘。$3^{(n / 3)}$
3. 如果模3的余数是1的话,就拿出一个3和余数1组成4,再和剩下的3相乘。$4 * 3^{n / 3 - 1}$
4. 如果模3的余数是2的话,就将这个2和所有的3相乘。 $2 * 3^{n / 3}$。
5. 为什么只有3种情况,因为所有数模3只有3种情况(0, 1, 2)
6. 可以特判一下2和3,因为结果显而易见。
class Solution {
public int maxProductAfterCutting(int length) {
if(length == 2) return 1;
if(length == 3) return 2;
if(length % 3 == 0) return (int)Math.pow(3, length / 3);
else if(length % 3 == 1) return 4 * (int)Math.pow(3, length / 3 - 1);
else return 2 * (int)Math.pow(3, length / 3);
}
}