$\color{red}{DP}$——目录

题目大意：

小明手里有 $n$ 元钱 全部 用来买书，书的价格为 $10$ 元，$20$ 元，$50$ 元，$100$ 元。
问小明有多少种买书方案？（每种书可购买多本）

解题方法：

首先我们看到这句话：每种书可购买多本就知道这是完全背包的变形。
我们设 $a$ 数组分别为所有书的价格，接着就是一个完全背包求方案数
$$闫氏DP分析法$$

1. 状态表示——集合：$f[i][j]$ 表示考虑前 $i$ 个数字，且总数字和恰好 $j$ 的集合下能获得的方案数。
2. 状态表示——属性：因为是求方案数，故为 $count$，也就是和。
3. 状态计算——集合划分：考虑第 $i$ 个数选不选。
   • 不选或选不了（剩余数量不够 $j < a[i]$）：$f[i - 1][j]$。
   • 选：$f[i][j - a[i]]$。首先你对第i个数字进行了你的抉择，但是因为完全背包优化的缘故，所以前一维还是 $i$，接着因为使用了 $a[i]$ 的价钱，所以应该是 $j - a[i]$。

好了这样就完事了。

完整代码，时间复杂度：$O(nm)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int f[6][1010];
int a[6] = {0, 10, 20, 50, 100};

int main()
{
    cin >> n;
    f[0][0] = f[1][0] = f[2][0] = f[3][0] = f[4][0] = 1;
    for (int i = 1; i <= 4; i ++ ) {
        for (int j = 0; j <= n; j ++ ) {
            f[i][j] = f[i - 1][j];
            if (j >= a[i]) f[i][j] += f[i][j - a[i]];
        }
    }
    cout << f[4][n] << endl;
    return 0;
}

当然也可以优化成一维的。

完整代码，时间复杂度：$O(nm)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int f[1010];
int a[6] = {0, 10, 20, 50, 100};

int main()
{
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= 4; i ++ ) {
        for (int j = a[i]; j <= n; j ++ ) {
            f[j] += f[j - a[i]];
        }
    }
    cout << f[n] << endl;
    return 0;
}