整数拆分

问题描述

---

一个正整数N,将其拆分成任意个正整数，使得所有的正整数乘机最大化
N=n1+n2+n3+…+n(i-1) + ni; (0<i<=N)
n1n2n3…n(i-1) ni 乘积最大

---

问题分析

---

递归性质
f代表数字n分成i个正整数可以获得的最大乘积
f(n,i) = f(n-j,i-1) * j (0<j<n-i)
f(n) = max(f(n,1),f(n,2),… f(n,i-1),f(n,(i)))

f代表数字n可以获得的最大乘积
fi代表数字n获得最大乘积时要拆分的个数
f(n)=max(f(n-j) * j) (0<j<n-j)
fi(n)=fi(n-j) + 1

---