给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

    示例 1:

    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。
    示例 2:

    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
    说明: 你可以假设 n 不小于 2 且不大于 58。

    1. class Solution {
    2. public:
    3.     // 数学解法：
    4.     // 将n分解成尽可能多(m)的3；
    5.     /*
    6.     if n = 3*m, max = pow(3, m);
    7.     if n = 3*m + 1, 分解成：3 * (m-1) + 4, max = pow(3, m-1) * 4;
    8.     if n = 3*m + 2, max = pow(3, m) * 2;
    9.     */
    10.     /*
    11.     int integerBreak(int n) {
    12.         if (n <= 3)
    13.             return n-1;
    14.         int m = n / 3;
    15.         int t = n % 3;
    16.         if (0 == t)
    17.             return (int)pow(3, m);
    18.         else if(1 == t)
    19.             return int(pow(3, m-1)) << 2;
    20.         else
    21.             return int(pow(3, m)) << 1;
    22.     }
    23.     */
    25.     // 动态规划
    26.     int integerBreak(int n) {
    27.         int * dp = new int[n+1];
    28.         dp[0] = 0;
    29.         dp[1] = 0;
    30.         dp[2] = 1;
    31.         for(int i=3; i<=n; ++i){
    32.             dp[i] = max(max(2*(i-2), 2*dp[i-2]), max(3*(i-3), 3*dp[i-3]));
    33.         }
    34.         return dp[n];
    35.     }
    36. };