解题思路：有动态规划和贪心两种方法。

  • 贪心
    通过打表我们发现这样的规律：一个数拆分达到最大一定是其拆乘3的个数达到最大，但如果结尾剩下1的话要少拆1个3从而拼成1个4。
  • 动态规划
    dp[i]：表示将长度为i的线段裁剪为m段的乘积最大值 (2 <= m <= n)
    转移方程：dp[i] = dp[j] * dp[i-j] (1 <= j <= i/2)
class Solution {
public:
    int maxProductAfterCutting(int length) {
        return Solve_2(length);
    }
    
    int Solve_1 (int len) {
        /** * dp[i] : 表示将长度为i的线段裁剪为m段的乘积最大值 (2 <= m <= n) * 转移方程 : dp[i] = dp[j]*dp[i-j] (1 <= j <= i/2) ::至少两段(i/2,i-i/2) 最多n段(1,...,1) */
        if (len < 4) {
            return len-1;
        }
        vector<int> dp(len+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= len; i++) {
            for (int j = 1; j <= i/2; j++) {
                dp[i] = max(dp[i], dp[j]*dp[i-j]);
            }
        }
        int res = 0;
        for (int i = 4; i <= len; i++) {
            res = max(res, dp[i]);
        }
        return res;
    }
    
    int Solve_2 (int len) {
        /** * 贪心 ： * len = 1, res = 1 * len = 2, res = 1 * len = 3, res = 2 * len = 4, res = 4 (2*2) * len = 5, res = 6 (2*3 || 3*2) * len > 5, res = 3^(len/3)*(剩下的数(>1)) * 我们发现若要让乘积越大，必定要将数拆出的3的个数尽量多,不过当剩下为1的时候前一个不能拆乘3要转乘2*2 */
         if (len < 4) {
             return len-1;
         }
         if(len == 4) {
             return 4;
         }
         if (len % 3 == 1) {
             return pow(3, len/3-1)*4;
         }
         return pow(3, len/3)*(len-len/3*3 == 0?1:2);
    }
};