信息学里面动态规划算法里面专门有例子讲整数拆分的。

求正整数之和为n 拆分后的最大积是多少？

用 f[i] 代表 整数和为i的时候拆分出的整数最大积
那么边界值就是 f[1] = 1 , f[2] =2 ,f[3] = 3; f[4] = 4;
当 n>4的时候后，假设对 i 拆除的第一个数是 j （ 0<j<i) ,那么有两种情况

第一种： i-j 不在继续拆分， 那么 f[i] = j*(i-j);
第二种： i-j 还可以继续拆， 那么 f[i] = j * f[i-j];

这样，只要去这两种情况里面的最大值就可以了。
状态转移就是 f[i] = max(j*(i-j),j*f[i-j]);

代码是
f[1] = 1 ;
f[2] = 2;
f[3] = 3;
f[4] = 4;
for (int i=5;i<=n;i++) {
     for (int j=1;j<i;j++) {
         f[i] = max(f[i] ,max(j * (i - j), j * f[i - j]));
        }
    }
cout << f[n];

还有像上面版友说的用均值定理，对等分以后的表达式求导，算出e是最大，而3比2更接近e，

所以状态转移就成了一个简单的递推 f[i] = 3 * f[i-3]
这比上面 O（n^2）的算法更快。

for (int i=5;i<=n;i++) {
    f[i] = 3*f[i-3];
}
cout << f[n];


【 在 diracsea 的大作中提到: 】
: 前些天我看了同事发给我的她家娃四年级的奥数资料，感觉还是有些套路的…比如两个数的和一定求积的最大值问题，就是用一个结论：和一定时两数差越小积越大…这会还没有讲多项式乘法，怎么讲原理？
: 然后这个专题居然引申到了多个数的和一定，求积的最值。比如几个数的和为16，求这几个数积的最大值问题。这个是不是也沿用上面提到的两个数时的性质呢？老师给的口诀是多个数和一定，尽量拆更多的3，不要拆2…请问他如何讲原理？
: 发自「今日水木 on iOS」
--
FROM 120.244.220.*