Project Euler 76

题目

Counting summations

It is possible to write five as a sum in exactly six different ways:

\(\begin{aligned} &4+1\\ &3+2\\ &3+1+1\\ &2+2+1\\ &2+1+1+1\\ &1+1+1+1+1 \end{aligned}\)

How many different ways can one hundred be written as a sum of at least two positive integers?

解决方案

本体是一个明显的动态规划。

令\(n=100\)，记录状态\(f(i,j)(1\leq i\leq n,0\leq j\leq n)\)为：当前已经使用了前\(1\sim i\)中所有数，可以凑得和为\(j\)的方案数。可写出如下状态转移方程：

\[ f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad j=0 \lor i=1 \\ &f(i-1,j) & & \text{else if}\quad j<i \\ &f(i-1,j)+f(i,j-i) & & \text{else} \end{aligned}\right. \]

对于最后一题式子，有两种转移方式：

1. 不使用第\(i\)个数，直接把使用前\(i-1\)个数的情况记录下来。
2. 使用第\(i\)个数，无论之前如何，直接把\(f(i,j-i)\)中的所有方案都添加一个\(i\)，就变成了现在的方案。

代码

N = 100
f = [0 for _ in range(N + 1)]
f[0] = 1
for i in range(1, N + 1):
    for j in range(i, N + 1):
        f[j] += f[j - i]
ans = f[N] - 1
print(ans)