问题描述:设n是一个正整数,将n分解为若干互不相同的自然数之和,且使这些自然数的乘积最大。 本讲义提供该问题的正确算法的自然语言描述及其严格证明。

Dynamic Programming动态规划方法采用最优原则来建立用于计算最优解的递归式,并且考察每个最优决策序列中是否包含一个最优子序列,这里我们就来展示C语言使用DP动态规划思想解最大K乘积与乘积最大问题

最大K乘积问题 设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。 编程任务： 对于给定的I 和k，编程计算I 的最大k 乘积。 需求输入： 输入的第1 行中有2个正整数n和k。正整数n是序列的长度；正整数k是分割的段数。接下来的一行中是一个n位十进制整数。（n<=10） 需求输出： 计算出的最大k乘积。 解题思路：DP 设w(h,k) 表示: 从第1位到第K位所组成的十进制数,设m(i,j)表示前i位(1-i)分成j段所得的最大乘积,则可得到如下经典的DP方程： if(j==1)