解题思路

设 $f(i)$ 为用若干个数（每次可取 $1..i$ 中不超过剩余的整数）按顺序恰好凑成和为 $i$ 的方案数。最后一步取值为 $t\in[1,i]$ 时，前缀必须凑成 $i-t$。因此有纯二重循环的 DP 递推：

实现上：

题面描述

本题在“每次取 1 或 2 凑成 $n$”与“每次取 1、2 或 3 凑成 $n$”的基础上进一步扩展： 给定一个非负整数 $n$。每次可取一个正整数，取值范围为 $1$ 到 $n$，将若干个数相加恰好得到 $n$。两种方案只要在某个位置取的数不同，就视为不同（即顺序有区分）。求不同方案数。

记答案为 $f(n)$。

输入格式

• 第一行一个整数 $n$。

输出格式

• 输出一行一个整数：$f(n)$。

数据范围

• $0 \le n \le 60$

样例

样例输入

4

样例输出

8

说明

• 对于 $n=4$，所有顺序不同的分解（每次可取 $1..4$，但不超过剩余）共有 8 种，分别是：

1. $1+1+1+1$
2. $1+1+2$
3. $1+2+1$
4. $2+1+1$
5. $2+2$
6. $1+3$
7. $3+1$
8. $4$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写