整数划分——DP

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133710641

用 $j$ 个数表示 $i$ 的方案数，考虑dp

转移考虑最小值是否为1

无限制

1. 若为1，则转移到 $f(i+1, j+1)$

2. 不为1，则全部+1，转移到 $f(i+j, j)$

数之间不能重复

那么相当于每次整体+1

1. 若为1，转移到 $f(i+j+1, j+1)$

2. 不为1，转移到 $f(i+j, j)$

数的上界有限制

考虑 $f(i,j)$ 所有数都合法，我们现在整体+1，那么不合法的数只会变成 $n+1$

而我们在上面保证数两两不同，所以我们可以直接让 $f(i,j)-=f(i-(n+1),j-1)$ ，相当于钦定一个数为 $n+1$

题目： https://www.luogu.com.cn/problem/P4104