将五表示成整数之和总共有六种方式：
\[ \begin{aligned}&4 + 1\\&3 + 2\\&3 + 1 + 1\\&2 + 2 + 1\\&2 + 1 + 1 + 1\\&1 + 1 + 1 + 1 + 1\end{aligned} \]
将一百写成至少两个正整数之和总共有多少种方式？
分析：这道题实际上就是数论中著名的整数拆分问题，很多著名的数学家如欧拉、哈代与拉马努金都曾研究过这个问题。对于特定的正整数\(n\)，把它拆分成正整数之和的方法数叫做分割函数，一般记为\(p(n)\)。进一步的，我们把一个正整数\(n\)用小于等于\(k\)的正整数表示的方法数记为\(p(n,k)\)，则\(p(n)=p(n,n)\)。题目所求把一个正整数表示成至少两个正整数之和的方法数实际上就是\(p(n,n-1)\)，如\(p(5,4)=6,p(5,3)=5,p(5,2)=3,p(5,1)=1\)。
这道题实际上和第三十一题是非常类似的，都属于一类集合拆分问题，因此可以用动态规划的方法加以解决。如对于题目给出的例子，\(p(5,2)\)表示把五写成不大于二的正整数的方法数，我们知道有三种方法，如下：
\[
\begin{aligned}&2 + (2 + 1)\\&2 + (1 + 1 + 1)\\&1 + 1 + 1 + 1 + 1\end{aligned}
\]
我们可以把这三种方法分为两类：一类是用不包括二的正整数，也即用一来表示五，即为\(p(5,1)=1\)；第二类是包括二的正整数来表示五，这个方法数是多少了？因为我们已经知道这个和式中必然包括二，则可以表示成为\(5=2+x\)的方式，因此方法数应该是\(p(x,2)\)，也就是\(p(5-2,2)=p(3,2)\)。因此，我们有\(p(5,2)=p(5,1)+p(3,2)\)。一般地，我们有：
\[
p\left( n,k \right) =\begin{cases} 1& n=1\ or\ k=1\\ 1+p\left( n,k-1 \right)& n\le k\\ p\left( n,k-1 \right) +p\left( n-k,k \right)& n>k\\\end{cases}
\]
有了以上状态转移方程，我们就可以用从上至下或者从下至上的动态规划来解决这个问题，我这里只实现了从下至上的方式，代码如下：
# time cost = 2ms
from functools import lru_cache
@lru_cache(maxsize=2048)
def partition(i,j):
if i == 1 or j == 1:
return 1
elif i <= j:
return partition(i,i-1)+1
else:
return partition(i,j-1) + partition(i-j,j)
def main(N=100):
return partition(N,N-1)Project Euler 76: Counting summations
原文：https://www.cnblogs.com/metaquant/p/12036353.html