1 public class Solution 2     { 3         public int IntegerBreak(int n) 4         { 5             if (n == 2) 6             { 7                 return 1; 8             } 9             else if (n == 3)10             {11                 return 2;12             }13             var max = int.MinValue;14             for (int i = 2; i <= n / 2; i++)15             {16                 var div = n / i;17                 var mod = n % i;18                 var cur = 0;19                 if (mod == 0)20                 {21                     cur = Convert.ToInt32(Math.Pow(i, div));22                 }23                 else24                 {25                     var cur1 = Convert.ToInt32(Math.Pow(i, div - 1) * (i + mod));26                     var cur2 = Convert.ToInt32(Math.Pow(i, div)) * mod;27                     cur = Math.Max(cur1, cur2);28                 }29                 if (cur > max)30                 {31                     max = cur;32                 }33                 else34                 {35                     break;36                 }37             }38             return max;39         }40     }

 

这道题的解题思路是，从2到n/2每个值依次进行尝试，对于每一个值，计算这种情况下的因子乘积，

如果是可以被整除，则计算当前值的“倍数的次方”；如果不能被整除，则分两种情况分别计算。

第一种是：将某一个因子与余数合并为一个因子。

第二种是：剩余的余数做一个单独的因子。

每种情况都计算出其因子的乘积，然后找最大值。

举例来说，输入参数n=12，

i=2，执行21行，cur=2^6=64，更新max=64

i=3，执行21行，cur=3^4=81，更新max=81

i=4，执行21行，cur=4^3=64，保持max=81

i=5，执行25～27，cur1=5^(2-1) * (5+2)=5*7=35，cur2=5^2 * 2=5*5*2=50，cur=50，保持max=81

i=6，执行21行，cur=6^2=36，保持max=81

执行完毕，最终结果为81。

 

补充一个使用dp的解决方案：

1 public class Solution 2     { 3         public int IntegerBreak(int n) 4         { 5             int[] dp = new int[n + 1]; 6             dp[1] = 1; 7             for (int i = 2; i <= n; i++) 8             { 9                 for (int j = i-1; j >=1; j--)10                 {11                     var premax = dp[i - j];12                     var distance = i - j;13                     var cur = Math.Max(premax, distance) * j;14                     dp[i] = Math.Max(dp[i], cur);15                 }16             }17             return dp[n];18         }19     }