Algorithm2.6 计数dp
[TOC]
计数dp
典型：
- 对一个区域进行划分，划分种类
- 随意划分：P1025，直接给定一个数以及要划分的份数，然后看这个数有多少种分法
- 按照给定的要求划分：P1077，直接卡死了每一个点上的约定范围
- 按照递增/递减的方式划分：P1806，直接按照递增着划分
随意划分
https://www.luogu.com.cn/problem/P1025
按照给定要求划分
https://www.luogu.com.cn/problem/P1077
递增/递减划分
https://www.luogu.com.cn/problem/P1806
每一步都有可能是从任意之前的某一步跳过来的，因为只要保证递增就好了。也就是第一次是1次，那么第2次必定第一次的次数递增上来，那么第三次必定包括第一次和第二次递增上来。
=>每次只需要把自己前面所有的点的值都加起来即可
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 509;
ll n, dp[maxn];
int main() {
scanf("%lld", &n);
dp[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = n; j >= i; --j)
dp[j] += dp[j-i];
printf("%lld\n", dp[n]-1);
return 0;
}