题解 | #整数拆分#
整数拆分
http://www.nowcoder.com/questionTerminal/376537f4609a49d296901db5139639ec
大佬的题解：https://blog.nowcoder.net/n/043e10b721464753b19d8b55a86498cf
假设给定一个数N：
1.N是奇数，那么N拆分的时候必定有一个1，因为2的次幂除了1都是偶数，由很多偶数不可能构成奇数。
所以 f(N)=f(N-1)
举例：
5=（1+4）=（1+2+2）=（1+1+1+2）=（1+1+1+1+1） ;一共有四种拆分形式
4=（4） =（2+2） =（1+1+2） = (1+1+1+1) ;一共四种拆分方式
2.N是偶数，那么可以分成两种情况：
2.1 N中拆分出1，N中拆分出1和上边N是奇数的情况一样，即f(N-1)
举例：
4=（4）=（2+2）=（1+1+2）=（1+1+1+1）
3=（1+2）=（1+1+1）
2.2 N中不拆分出1
不拆分出1，即都是偶数，偶数的性质可知，偶数都可以整除2，假如N的和为2m，那么除2之后变成m，但是并不影响f(N)。
举例：
4=（4）=（2+2） 都不包含1
同理，由2.1和2.2两种情况的结果相加得到完整的4的拆分。
也就是说N为偶数的情况就是f(N)=f(N-1)+f(N/2)
查看15道真题和解析